题目描述

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$）取模。

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

• $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 翻译

样例

4
1
2
9
91234

1
12
830455698
890287984