Given an integer n, in how many ways you can tile a 4 × n rectangle with 3 × 1 tiles?
Because the answer can be large, we are interested in the remainder after answer is divided by 1000000007.
First line contains the number of test cases t (1 ≤ t ≤ 100). Each test case consist of a single line containing an integer n (1 ≤ n ≤ 10000).
For each test case print the the remainder after answer is divided by 1000000007.