Dexter wants to completely cover a 4 x N board using N tetrominoes. Every cell in the grid has to be covered by exactly one piece and no piece is allowed to go outside of the board. And no piece can be rotated or flipped.
A tetromino is a connected set of 4 tiles. All 19 possible tetrominoes that can be used (any number of times) are shown below:
Assume that all 19 pieces have different colors. Now your task is to find the total number of ways Dexter can cover the board. Two board configurations are different if a cell can be found where the colors are different.
Input
Input starts with an integer T (≤ 20), denoting the number of test cases.
Each case starts with a line containing an integer N (1 ≤ N ≤ 109).
Output
For each case, print the case number and the number ofways to fill the board modulo 100000007 (109 + 7).
Sample
| Sample Input | Sample Output |
|---|---|
4 1 2 3 12 | Case 1: 1 Case 2: 4 Case 3: 23 Case 4: 15747348 |