PRWAS - Prana and The Series

no tags 

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 nth 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 ≤105

1 ≤ n≤109

 

 

Output

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

 

 

Sample

Input

Output

3

1

2

3

1

25

101


hide comments

Added by:Abu Sufian
Date:2014-10-16
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64