쌍둥이 타워

최근 몇 년 사이 라이덴 대학교에 쌍둥이 학생이 너무 많이 입학하여, 이들의 기숙사 배정이 큰 문제가 되었습니다. 모두를 수용하기 위해 대학교는 $N$개 층으로 이루어진 고층 건물을 짓기로 했습니다. 각 층에는 방이 $3 \times 3$ 정사각형 형태로 9개씩 배치됩니다. 모든 학생은 자신의 쌍둥이 형제자매와 바로 옆, 바로 위, 또는 바로 아래 방을 배정받을 수 있어야 합니다. 더 정확히 말하면, 한 쌍둥이가 쓰는 두 방은 하나의 벽을 사이에 두고 맞닿아 있거나, 한 방의 바닥이 다른 방의 천장이어야 합니다. 사생활 보호를 위해 학생들은 방을 함께 쓰지 않습니다.

어떤 방도 짝이 없이 남지 않도록 모든 방을 둘씩 짝지을 수 있는 경우의 수를 $10007$로 나눈 나머지를 구하세요.

첫째 줄에 테스트 케이스의 개수 $T$가 주어집니다. 각 테스트 케이스는 정수 $N$ 하나로 이루어진 한 줄이며, $0 \le N \le 5000$을 만족합니다.

각 테스트 케이스마다, 가능한 짝짓기의 경우의 수를 $10007$로 나눈 나머지를 한 줄에 하나씩 출력하세요.