Constructing Chimney

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 case, please output a line which is "Case X: Y ", X means the number of the test case and Y means the remainder divided by 1000000007 of the answer.

2
1
2

Case 1: 2
Case 2: 49

2012 Multi-University Training Contest 4