Time Limit: 40000/20000 MS (Java/Others)

Memory Limit: 65536/32768 K (Java/Others)

Now we are planning to construct a big chimney. The chimney’s section is a 3*3 square and the center of it will have nothing like the picture below. Now we only have a lot of bricks whose size if 1*1*2, and we want to build a chimney whose height is N, so can help us to calculate how many ways we can build the chimney? The answer may be very large, so you can just tell the answer’s remainder divided by 1000000007.

The first line of the input contains an integer T (1<=T<=10) which means the number of test cases.

For each test cases, there is only one line with an integer N (1<=N<=10^9) which means the height of the chimney we want to build.

For each test cases, there is only one line with an integer N (1<=N<=10^9) which means the height of the chimney we want to build.

提交代码