You're given $n$. Find the value of $g(n)$.
$n$
$g(n)$
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$).
$T$
$0 < T \le 10^6$
$1 \le n \le 10^6$
For each case, print the value of $g(n)$ modulo $1000000007$.
$1000000007$
3 1 16 1000000
1 987 918091266