Time Limit: 1000ms Memory Limit: 65536k

## Description

A dominoes is a 1*2 rectangle. GLC want to fill a 4*N rectangle with
dominoes. And more, there does not exist such a vertical line that
can divide the rectangle into two non-empty parts and do not divide
any dominoes into two non-empty parts. (empty means area is zero).
For example:
11 11 11 12 12
22 22 23 12 12
33 34 23 33 34
44 34 44 44 34
When N is 2, there are 5 methods to tile the rectangle. But the last one does
not satisfy the requirement. If we draw a vertical line in the middle,
the rectangle is divided into two parts. The left is dominoes {1, 3}, and the
right is {2, 4}.
Given N, how many methods to tile the rectangle?
## Input

The first line is an integer T stands for the number of test cases.
Then T lines follow, and each line is a test case with an integer N.
Constraints:
T is in the range of [1, 3000].
N is in the range of [1, 1000000000].
## Output

For each test case output the answer in a single line. (Output the remainder
divided by 1000000007)
## Sample Input

2
1
2
## Sample Output

1
4
## Author

baihacker
## Tester

huangshenno1