The board is a rectangle of unit cells with N rows and N columns. At first, cells are empty. ?? has infinite blocks with the size of 2*2. ?? can put blocks in the board as long as no two blocks overlap. ?? wants to know how many different ways to fill the board, not necessary full. Two ways are consider same if they are same by rotating.
The first line of the input gives the number of test cases T; T test cases follow.
Each test case consists of one integers N, as described on the description above.
limits
T <= 20
1 <= N <= 20
For each test case, output one line containing “Case #x: y” (without quotes) , where x is the test case number (starting from 1) and y is the answer you get for that case, since the answer may be too large, you should output the it modulo 1000000007 (1e9 + 7).