← 返回题目列表

Codeforces · 1777/B

B. 埃莫德尼拉普

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

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

给定 $$$n$$$ 数字的排列 $$$p$$$,我们创建一个由 $$$2n$$$ 数字组成的数组 $$$a$$$,它等于 $$$p$$$ 与其反向连接。然后我们将 $$$p$$$ 的美感定义为 $$$a$$$ 中的反转数量。

数组 $$$a$$$ 中的反转数量是索引对 $$$i$$$、$$$j$$$ 的数量,使得 $$$i < j$$$ 且 $$$a_i > a_j$$$。

例如,对于排列 $$$p = [1, 2]$$$,$$$a$$$ 将是 $$$[1, 2, 2, 1]$$$。 $$$a$$$ 中的反转是 $$$(2, 4)$$$ 和 $$$(3, 4)$$$(假设基于 1 的索引)。因此,$$$p$$$ 的美丽在于$$$2$$$。

你的任务是找到大小为 $$$n$$$ 的所有 $$$n!$$$ 排列的美丽总和。打印该值除以 $$$1\,000\,000\,007$$$ ($$$10^9 + 7$$$) 得到的余数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。

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

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

输出

对于每个测试用例,打印一个整数 — 所有大小为 $$$n$$$ 的排列的美度总和以 $$$1\,000\,000\,007$$$ ($$$10^9 + 7$$$) 为模。

示例

输入 #1

3
1
2
100

输出 #1

0
4
389456655

注意

对于示例的第一个测试用例,$$$p = [1]$$$ 是唯一的排列。 $$$a = [1, 1]$$$ 具有 $$$0$$$ 反转。

对于示例的第二个测试用例,排列为 $$$[1, 2]$$$ 和 $$$[2, 1]$$$。它们各自的 $$$a$$$ 数组是 $$$[1, 2, 2, 1]$$$ 和 $$$[2, 1, 1, 2]$$$,两者都有 $$$2$$$ 反转。