Functions Are Beautiful

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

3
1
16
1000000

1
987
918091266