← 返回题目列表

Codeforces · 1581/A

A. CQXYM 计数排列

中文机器翻译题面 查看原题

CQXYM 正在计算 $$$2n$$$ 的排列长度。

排列是一个数组,由 $$$n$$$ 不同的整数组成,从 $$$1$$$ 到 $$$n$$$ 以任意顺序排列。例如,$$$[2,3,1,5,4]$$$ 是一个排列,但 $$$[1,2,2]$$$ 不是排列($$$2$$$ 在数组中出现两次),$$$[1,3,4]$$$ 也不是排列($$$n=3$$$ 但数组中有 $$$4$$$)。

仅当满足$$$p_i<p_{i+1}$$$的$$$i$$$个数不少于$$$n$$$时,才会计算排列$$$p$$$($$$2n$$$的长度)。例如:

- 排列 $$$[1, 2, 3, 4]$$$ 会被计算在内,因为 $$$p_i<p_{i+1}$$$ 的 $$$i$$$ 的数量等于 $$$3$$$ ($$$i = 1$$$, $$$i = 2$$$, $$$i = 3$$$)。
- 排列 $$$[3, 2, 1, 4]$$$ 不会被计算在内,因为 $$$p_i<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$$$。

输入

输入由多个测试用例组成。

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

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

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

输出

对于每个测试用例,将答案打印在一行中。

示例

输入 #1

4
1
2
9
91234

输出 #1

1
12
830455698
890287984

注意

$$$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].$$$