Limits 1s, 512 MB

You're given $n$. Find the value of $g(n)$.

Input

Input starts with an integer $T$ ($0 < T \le 10^6$) denoting the number of test cases.
Each of the next $T$ lines contains an integer $n$ ($1 \le n \le 10^6$).

Output

For each case, print the value of $g(n)$ modulo $1000000007$.

Sample

InputOutput
3
1
16
1000000
1
987
918091266

Submit

Login to submit.

Statistics

92% Solution Ratio
ovis96Earliest, Jul '17
Kuddus.6068Fastest, 0.1s
nusuBotLightest, 9.3 MB
hredhayxzShortest, 282B
Toph uses cookies. By continuing you agree to our Cookie Policy.