## 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**