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

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).

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

3
1
2
3

2
9 
32