CF1581A.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 \lt 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 \lt 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 \lt 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 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$.

CQXYM 正在统计长度为 $2n$ 的排列的个数。

排列是指由 $1$ 到 $n$ 中 $n$ 个互不相同的整数按任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（数字 $2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（此时 $n=3$，但数组中出现了 $4$）。

一个长度为 $2n$ 的排列 $p$ 仅当满足条件：使得 $p_i \lt p_{i+1}$ 成立的下标 $i$ 的个数不少于 $n$ 时，才被计入总数。例如：

• 排列 $[1, 2, 3, 4]$ 会被计入，因为满足 $p_i \lt p_{i+1}$ 的 $i$ 的个数为 $3$（即 $i = 1$、$i = 2$、$i = 3$）。
• 排列 $[3, 2, 1, 4]$ 不会被计入，因为满足 $p_i \lt p_{i+1}$ 的 $i$ 的个数仅为 $1$（即 $i = 3$）。

CQXYM 希望你帮他计算满足上述条件的排列个数，并对 $1000000007$（即 $10^9+7$）取模。

此外，取模运算 是指求余数。例如：

• $7 \mod 3=1$，因为 $7 = 3 \cdot 2 + 1$，
• $15 \mod 4=3$，因为 $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$

输入包含多个测试用例。

第一行包含一个整数 $t (t \geq 1)$ —— 测试用例的数量。随后是各测试用例的描述。

每个测试用例仅有一行，包含一个整数 $n(1 \leq n \leq 10^5)$。

保证所有测试用例中 $n$ 的总和不超过 $10^5$。

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

对于每个测试用例，在一行中输出答案。

$n=1$, there is only one permutation that satisfies the condition: $[1,2].$

In permutation $[1,2]$, $p_1 \lt p_2$, and there is one $i=1$ satisfy the condition. Since $1 \geq n$, this permutation should be counted. In permutation $[2,1]$, $p_1 \gt p_2$. Because $0 \lt n$, this permutation should not be counted.

$n=2$, there are $12$ permutations: $[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,3,4,2],[1,4,2,3],[2,1,3,4],[2,3,1,4],[2,3,4,1],[2,4,1,3],[3,1,2,4],[3,4,1,2],[4,1,2,3].$

$n=1$ 时，仅有一个排列满足条件：$[1,2]$。

在排列 $[1,2]$ 中，$p_1 \lt p_2$，且存在一个 $i=1$ 满足条件；由于 $1 \geq n$，该排列应被计入。在排列 $[2,1]$ 中，$p_1 \gt p_2$；由于 $0 \lt n$，该排列不应被计入。

$n=2$ 时，共有 $12$ 个排列：$[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,3,4,2],[1,4,2,3],[2,1,3,4],[2,3,1,4],[2,3,4,1],[2,4,1,3],[3,1,2,4],[3,4,1,2],[4,1,2,3]$。