## Get Ai

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 13   Accepted Submission(s): 10
Problem Description

Rcently, Xiaoxi notice a interesting sequence of number, which can be construct in a function below:

```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绍兴联赛