22313_TheTwinTower

In recent years so many twins enrolled at Leiden University, that housing them has become a big problem. In an effort to accomodate everyone, the university has made plans to build a skyscraper of N floors high, with 9 rooms on each floor, laid out in a 3×3 square. According to these plans, everyone should be able to get a room next to or directly above or below their twin brother or sister. To be even more precise: the two rooms of a twin should either be at opposite sides of a common wall, or the floor of one room should be the ceiling of the other. For the sake of privacy, students never share a room.

Today the university has tasked some poor soul (you!) to count all possible pairings of rooms that leave no room unpaired, modulo 10,007.

The first line of the input contains a single number: the number of test cases to follow. Each test case has the following format:

One line with an integer N, satisfying 0 ≤ N ≤ 5,000.

For every test case in the input, the output should contain a single number, on a single line: the number of possible configurations modulo 10007.

4
2
4
1576
2680

229
7728
229
7728