Problem C: How Many... in 3D!

Given a 2x2xN box, in how many ways can you fill it with 1x1x2 blocks?

Input Format

The input starts with an integer T - the number of test cases (T <= 10,000). T cases follow on each subsequent line, each of them containing the integer N (1 <= N <= 1,000,000).

Output Format

For each test case, print the number of ways to fill the box modulo 1,000,000,007

Sample Input

3
1
2
3

Sample Output

2
9
32