ITX351 wants to pave a $2 \times N$ road, for which he bought $N$ bricks of size $2 \times 1$. However, one of the bricks broke in half during transport, becoming two $1 \times 1$ bricks!
ITX351 has come up with an evil idea: he wants to place the two $1 \times 1$ bricks on this road such that they are not adjacent (i.e., they do not share an edge). The other bricks can be placed arbitrarily until the entire road is paved. This will surely drive his friend sea5, who has obsessive-compulsive disorder, crazy!
Perhaps you have already guessed the rest of the story—he is so excited about this that he cannot even type on his keyboard. Therefore, he asks you to help him calculate how many ways he can make his scheme succeed.
Input
The first line contains a positive integer $T$, representing the number of test cases. Note that each test case is independent.
The next $T$ lines each contain a positive integer $N$, representing the length of the road for that test case.
Output
For each test case, output a single integer representing the number of valid ways, modulo $1000000007$ ($10^9 + 7$).
Examples
Input 1
3 1 2 4
Output 1
0 0 6
Note
The following image shows all valid configurations for $N = 4$.
Constraints
The range and characteristics of all test data are shown in the table below:
| Test Case ID | $N$ Range | $T$ Range | Note |
|---|---|---|---|
| 1 | $N \le 10$ | $T \le 10$ | None |
| 2 | $N \le 10^5$ | $T \le 50$ | None |
| 3 | $N \le 10^5$ | $T \le 50$ | None |
| 4 | $N \le 10^5$ | $T \le 50$ | None |
| 5 | $N \le 10^5$ | $T \le 50$ | None |
| 6 | $N \le 2 \times 10^9$ | $T \le 50$ | None |
| 7 | $N \le 2 \times 10^9$ | $T \le 50$ | None |
| 8 | $N \le 2 \times 10^9$ | $T \le 50$ | None |
| 9 | $N \le 2 \times 10^9$ | $T \le 500$ | None |
| 10 | $N \le 2 \times 10^9$ | $T \le 500$ | None |