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.
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).
For each test case print the the remainder after answer is divided by 1,000,000,007.
3 3 6 3333
3 13 524313417