C. Counting heroes
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The evil math magician Matematicus is about to destroy the world! and he has given Ana, Beto and Carlos a last chance to defeat him. He will give them a number $$$N$$$ and each one of them will guess a random number between $$$1$$$ and $$$N$$$, and if the number guessed by Ana and by Beto added equals the number guessed by Carlos, they'll pass the test. If they manage to do this $$$k$$$ times, the world will be saved.

To make it more interesting Matematicus used his magic to ensure that the number that Ana guesses is smaller than the number guessed by Beto, and that the number guessed by Beto is smaller than the number guessed by Carlos. Our heros have asked you, what's the probability the world will be saved by them?

Input

On the first line a number $$$k$$$, ($$$1\leq k\leq 10^6$$$) the number of times they'll have to do the test. On the next $$$k$$$ lines, a number $$$N_i$$$($$$3\leq N\leq 10^6$$$) the $$$i$$$-th number given by Matematicus.

Output

$$$k$$$ lines, in the $$$i$$$-th line a number representing the probability that they passed the first $$$i$$$ tests. It can be proven that the answer can be represented as a rational number $$$\frac{p}{q}$$$ with coprime $$$p$$$ and $$$q$$$. You need to output $$$p \cdot q^{-1}$$$ mod $$$10^{9}+7$$$.

Examples
Input
1
3
Output
1
Input
3
3
5
10
Output
1
800000006
466666670