Problem B: Counting Again?

Given an integer N, in how many ways you can tile a 4 x N rectangle with 3 x 1 tiles? Because the answer can be large, we are interested in the remainder after answer is divided by 1,000,000,007.

Input Format

First line of the input contains an integer T (1 <= T <= 100) - the number of test cases. Each test case consist of a single line containing an integer N (1 <= N <= 10,000).

Output Format

For each test case print the the remainder after answer is divided by 1,000,000,007.

Sample Input

3
3
6
3333

Sample Output

3
13
524313417

Darko Aleksic
CCPC 2013