### H - Round table

##### Languages: C, C++, Java, Python, ... (details)

Consider $2\cdot n$ people with $n$ enemy pairs, Each person has exactly one enemy and the enmity is bi-directional, meaning that, if $a$ is the enemy of $b$, then $b$ is the enemy of $a$. Enemy pairs are defined as follows, for all $j$ ($1 \leq j \leq n$), the person $2 \cdot j - 1$ and the person $2 \cdot j$ are enemies.

You want to calculate in how many ways it is possible to distribute them on a large circular table with $2 \cdot n$ seats, so that there are no 2 enemies sitting next to each other.

The seats are numbered from $1$ to $2 \cdot n$. The seats of positions $i$ and $i + 1$ are adjacent for all $1 \leq i <2 \cdot n$. The seats $1$ and $2 \cdot n$ are also adjacent. Two distributions are considered different if they have at least one seat occupied by different people in each distribution.

For example:
We have 4 people and the enemy pairs are $(1, 2)$ and $(3, 4)$. There are 8 different ways to place them around the table:

$\bullet (1, 3, 2, 4) \qquad \qquad \bullet (2, 3, 1, 4)\qquad \qquad \bullet(3, 1, 4, 2)\qquad \qquad \bullet (4, 1, 3, 2)$
$\bullet (1, 4, 2, 3)\qquad \qquad \bullet (2, 4, 1, 3) \qquad \qquad \bullet(3, 2, 4, 1)\qquad \qquad \bullet (4, 2, 3, 1)$

#### Input

The first line of the input contains an integer $t$ $(1 \leq t \leq 10^5)$, the number of cases to process. The next $t$ lines describe the test cases, each with an integer $n$ $(1 \leq n \leq 10^5)$, the number of enemy pairs.

#### Output

For each test case you should print a line with the number of possible distributions. Since this number can be very large, print the remainder left by dividing it by $10^9 + 7$.

#### Sample test(s)

Input
4 1 2 4 99999
Output
0 8 11904 720034323