A14660 | CQXYM Count Permutations

CQXYM is counting permutations length of $2n$ .

A permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ( $2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ( $n=3$ but there is $4$ in the array).

A permutation $p$ (length of $2n$ ) will be counted only if the number of $i$ satisfying $p_i<p_{i+1}$ is no less than $n$ . For example:

- Permutation $[1, 2, 3, 4]$ will count, because the number of such $i$ that $p_i<p_{i+1}$ equals $3$ ( $i = 1$ , $i = 2$ , $i = 3$ ).
- Permutation $[3, 2, 1, 4]$ won't count, because the number of such $i$ that $p_i<p_{i+1}$ equals $1$ ( $i = 3$ ).

CQXYM wants you to help him to count the number of such permutations modulo $1000000007$ ( $10^9+7$ ).

In addition, [modulo operation](https://en.wikipedia.org/wiki/Modulo_operation) is to get the remainder. For example:

- $7 \mod 3=1$ , because $7 = 3 \cdot 2 + 1$ ,
- $15 \mod 4=3$ , because $15 = 4 \cdot 3 + 3$ .

The input consists of multiple test cases.

The first line contains an integer $t (t \geq 1)$ — the number of test cases. The description of the test cases follows.

Only one line of each test case contains an integer $n(1 \leq n \leq 10^5)$ .

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$

For each test case, print the answer in a single line.