Constructing Chimney

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

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

Description

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.

Input

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.

Output

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.

Sample Input

2 1 2

Sample Output

Case 1: 2 Case 2: 49

Hint

zhoujiaqi2010

Source

2012 Multi-University Training Contest 4

提交代码