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.

Input

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

Output

For each test case print the the remainder after answer is divided by 1000000007.