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