기하학 문양

사람은 선사시대부터 물건과 건물을 장식해 왔다. 그 장식에서 가장 중요한 요소가 기하학 문양이고, 기하학 문양은 일상에서도 쉽게 눈에 띈다.

계산기하 전문가 수환이는 기하학 문양이 그리드와 여러 서브 그리드 위에서 아주 정교하게 만들어진다는 사실을 알아냈다. 수환이는 최근 기하학 문양을 자동으로 만드는 연구를 시작했다.

수환이가 관심을 두는 그리드는 직사각형 그리드와 원형 그리드이다. $m \times n$ 직사각형 그리드는 평면 위의 정점과 간선이 직사각형 격자를 이루는 그래프이다. 한 행에 놓인 정점은 $n$개, 한 열에 놓인 정점은 $m$개이다. 정점 집합은 $\{v^i_j : 0 \le i \le m-1,\ 0 \le j \le n-1\}$이고, 간선 집합은 $\{(v^i_j, v^p_q) : |i-p| + |j-q| = 1\}$이다. $m \times n$ 원형 그리드는 $m \times n$ 직사각형 그리드에 간선을 더해 양 끝을 이어 붙인 그래프이다. 즉 모든 $0 \le i \le m-1$에 대해 간선 $(v^i_{n-1}, v^i_0)$을 추가한다.

기하학 문양 중에는 그리드의 스패닝 트리를 이루는 것이 많다. 스패닝 트리는 그래프의 모든 정점과 일부 간선으로 이루어지고, 사이클이 없으면서 전체가 연결된 부분 그래프이다. 수환이는 $2 \times n$ 그리드에서 만들 수 있는 서로 다른 스패닝 트리의 개수를 세려고 한다. 정점은 모두 서로 구분되므로, 회전이나 대칭으로 겹쳐지는 두 스패닝 트리도 간선 집합이 다르면 서로 다른 것으로 센다.

$n$이 주어졌을 때, $2 \times n$ 직사각형 그리드와 $2 \times n$ 원형 그리드에서 만들 수 있는 스패닝 트리의 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어지는 $T$개의 줄에는 각 테스트 케이스의 정수 $n$이 한 줄에 하나씩 주어진다. ($3 \le n \le 50\,000$)

각 테스트 케이스마다 $R_n$을 $10\,007$로 나눈 나머지와 $C_n$을 $10\,007$로 나눈 나머지를 공백 하나로 구분해 한 줄에 출력한다. $R_n$은 $2 \times n$ 직사각형 그리드의 스패닝 트리 개수, $C_n$은 $2 \times n$ 원형 그리드의 스패닝 트리 개수이다.