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