← 返回题目列表

Codeforces · 1391/C

C. 循环排列

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

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

考虑长度为 $$$n$$$ 的排列 $$$p$$$,我们使用它构建一个大小为 $$$n$$$ 的图,如下所示:

- 对于每个 $$$1 \leq i \leq n$$$,找到最大的 $$$j$$$ 使得 $$$1 \leq j < i$$$ 和 $$$p_j > p_i$$$,并在节点 $$$i$$$ 和节点 $$$j$$$ 之间添加一条无向边
- 对于每个 $$$1 \leq i \leq n$$$,找到最小的 $$$j$$$,使得 $$$i < j \leq n$$$ 且 $$$p_j > p_i$$$,并在节点 $$$i$$$ 和节点 $$$j$$$ 之间添加一条无向边

如果不存在这样的 $$$j$$$ ,我们就不做边。另请注意,我们在相应索引之间创建边,而不是在这些索引处的值。

为了清楚起见,请考虑 $$$n = 4$$$ 和 $$$p = [3,1,4,2]$$$ 为例;这里,图的边是$$$(1,3),(2,1),(2,3),(4,3)$$$。

如果使用 $$$p$$$ 构建的图至少有一个简单循环,则排列 $$$p$$$ 是循环的。

给定 $$$n$$$,找到长度为 $$$n$$$ 的循环排列数。由于数字可能非常大,因此输出它对$$$10^9+7$$$取模。

简单循环的正式定义请参阅注释部分

输入

第一行也是唯一一行包含一个整数 $$$n$$$ ($$$3 \le n \le 10^6$$$)。

输出

输出单个整数 $$$0 \leq x < 10^9+7$$$,长度为 $$$n$$$ 模 $$$10^9+7$$$ 的循环排列数。

示例

输入 #1

4

输出 #1

16

输入 #2

583291

输出 #2

135712853

注意

$$$n = 4$$$ 有 $$$16$$$ 循环排列。 $$$[4,2,1,3]$$$ 就是这样一种排列,具有长度为四的循环:$$$4 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 4$$$。

如果满足以下条件,节点 $$$v_1$$$、$$$v_2$$$、$$$\ldots$$$、$$$v_k$$$ 形成一个简单循环:

- $$$k \geq 3$$$。
- $$$v_i \neq v_j$$$ 对于任何索引对 $$$i$$$ 和 $$$j$$$。 ($$$1 \leq i < j \leq k$$$)
- $$$v_i$$$ 和 $$$v_{i+1}$$$ 对所有 $$$i$$$ ($$$1 \leq i < k$$$) 共享一条边,并且 $$$v_1$$$ 和 $$$v_k$$$ 共享一条边。