Geometric Patterns

People have decorated objects and buildings since prehistoric times. The most important element in that decoration is the geometric pattern, and geometric patterns are easy to spot in everyday life.

Suhwan, an expert in computational geometry, found that geometric patterns are built with great precision on grids and on their subgrids. He recently started a research project that generates geometric patterns automatically.

The grids Suhwan cares about are the rectangular grid and the circular grid. An $m \times n$ rectangular grid is a graph whose vertices and edges form a rectangular lattice in the plane. Each row holds $n$ vertices and each column holds $m$ vertices. Its vertex set is $\{v^i_j : 0 \le i \le m-1,\ 0 \le j \le n-1\}$ and its edge set is $\{(v^i_j, v^p_q) : |i-p| + |j-q| = 1\}$. An $m \times n$ circular grid is the $m \times n$ rectangular grid with extra edges that wrap it around: for every $0 \le i \le m-1$, the edge $(v^i_{n-1}, v^i_0)$ is added.

Many geometric patterns form a spanning tree of the grid. A spanning tree is a subgraph that contains every vertex and some of the edges, has no cycle, and is connected. Suhwan wants to count the distinct spanning trees of a $2 \times n$ grid. Every vertex is distinguishable, so two spanning trees that coincide under a rotation or a reflection still count separately when their edge sets differ.

Given $n$, write a program that counts the spanning trees of the $2 \times n$ rectangular grid and the spanning trees of the $2 \times n$ circular grid.

The first line contains the number of test cases $T$. Each of the following $T$ lines contains one integer $n$. ($3 \le n \le 50\,000$)

For each test case, print $R_n$ modulo $10\,007$ and $C_n$ modulo $10\,007$ on one line, separated by a single space. $R_n$ is the number of spanning trees of the $2 \times n$ rectangular grid, and $C_n$ is the number of spanning trees of the $2 \times n$ circular grid.