**Problem Description**

int a[MAXN]; void build() { int cnt = 0; for (int i = 0; i <= n; i++) { a[i] = 2 * (cnt + 1); int u = cnt; for (int k = 1; k <= a[i]; k++) ++cnt; for (int h = 1; h <= u; h++) ++cnt; } }

Of course, some unavoidable arithmetic overflow will occur in the above construction function (that is, beyond the int range). Xiaoxi hopes you can improve the above procedure to avoid any possible arithmetic overflow.

After improvement, Xiao Xi wants to know the results after module 1000000007 (1e9 + 7) with the values of some items in the sequence (a[i]) .

**Input**

The first line of data is the number of cases T.(T<=50000).

Then T lines, each line contains a number n which means the nth number in above sequence a[] Xiaoxi want to know . 0 <= n <= 1e9

**Output**

For each query, print an integer respecting your answer in one line.

**Sample Input**

6 3 4 5 100 100000 1000000000

**Sample Output**

28 82 244 886041712 916902200 235939646

**Source**

2019绍兴联赛