CF1581A CQXYM Count Permutations

CQXYM 正在统计长度为 $2n$ 的排列。 排列是一个包含 $1$ 到 $n$ 的 $n$ 个互不相同整数的数组，顺序任意。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（$n=3$，但数组中有 $4$）。 一个长度为 $2n$ 的排列 $p$ 只有当满足 $p_i < p_{i+1}$ 的 $i$ 的个数不少于 $n$ 时，才会被统计。例如： - 排列 $[1, 2, 3, 4]$ 会被统计，因为满足 $p_i < p_{i+1}$ 的 $i$ 有 $3$ 个（$i=1,2,3$）。 - 排列 $[3, 2, 1, 4]$ 不会被统计，因为满足 $p_i < p_{i+1}$ 的 $i$ 只有 $1$ 个（$i=3$）。 CQXYM 想让你帮他统计满足条件的排列个数，答案对 $1000000007$（$10^9+7$）取模。 此外，[取模运算](https://en.wikipedia.org/wiki/Modulo_operation) 是取余数。例如： - $7 \bmod 3 = 1$，因为 $7 = 3 \cdot 2 + 1$， - $15 \bmod 4 = 3$，因为 $15 = 4 \cdot 3 + 3$。

输入包含多组测试数据。 第一行包含一个整数 $t$（$t \geq 1$），表示测试用例的数量。接下来每组测试用例仅一行，包含一个整数 $n$（$1 \leq n \leq 10^5$）。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

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

当 $n=1$ 时，只有一个排列满足条件：$[1,2]$。 在排列 $[1,2]$ 中，$p_1 < p_2$，有一个 $i=1$ 满足条件。由于 $1 \geq n$，该排列应被统计。在排列 $[2,1]$ 中，$p_1 > p_2$，因为 $0 < 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]$。 由 ChatGPT 4.1 翻译