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