Prana loves to find summation of any series. Today she has found one and now she is trying to find the sum of the first n terms.

The n^th term of the series is f(n). 

                                          f(n) = 1, when n=1

                              f(n)= ((n-1)*(8*(n–2)* 2+ 20)+4) , when n>1

 Suddenly her baby cried for some reason. So now she has to take care of her baby. Now she needs your help to find out the sum of the first n terms of the series i.e. f(1)+f(2)+…….+f(n).

Input

The first line contains an integer T i.e. number of test cases. Next T lines will contain an integer n.

T ≤10⁵

1 ≤ n≤10⁹

Output

Print the values corresponding to each test case. As the sum will be huge you have to print the result mod (10⁹+7).

Sample