## 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

*Darko Aleksic*

**ACPC 2011**