The Twin Tower

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 10, 007.