Filling

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).

5
1
2
3
4
5

Case #1: 1
Case #2: 2
Case #3: 2
Case #4: 12
Case #5: 84

In forth case, we have 12 different ways.(0 denotes unfilled,1 denoted filled)
0000 1100 0110 0000 1111 0000 1100 1100 1100 1111 1111 1111
0000 1100 0110 0110 1111 1111 1111 1100 1100 1111 1111 1111
0000 0000 0000 0110 0000 1111 0011 0011 0110 1100 0110 1111
0000 0000 0000 0000 0000 0000 0000 0011 0110 1100 0110 1111

FZU

2016 Multi-University Training Contest 4