The Twin Tower

Time limit1sMemory limit256 MB

Summary

Count perfect matchings of a 3x3xN grid graph where each of the 9N rooms pairs with an adjacent room, modulo 10007.

Level: Hard8 of 10
Topics: Dynamic programming, Bit manipulation, Matrix, Combinatorics
Solved: No attempts yet

Problem

In recent years so many twins have enrolled at Leiden University that housing them has become a big problem. To accommodate everyone, the university plans to build a skyscraper of $N$ floors, with 9 rooms on each floor laid out in a $3 \times 3$ square. Everyone must be able to get a room next to, directly above, or directly below their twin. More precisely, the two rooms of a twin must either lie on opposite sides of a common wall, or the floor of one room must be the ceiling of the other. For privacy, students never share a room.

Count all ways to pair up the rooms so that no room is left unpaired, modulo $10007$ .

Input

The first line contains a single integer $T$ : the number of test cases. Each test case is a single line containing one integer $N$ with $0 \le N \le 5000$ .

Output

For each test case, output on its own line the number of valid pairings, taken modulo $10007$ .

Examples3

Example 1
Input
```
4
2
4
1576
2680
```
Expected output
```
229
7728
229
7728
```
Example 2
Input
```
1
0
```
Expected output
```
1
```
Example 3
Input
```
1
2
```
Expected output
```
229
```