长度 $$$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$$$ 共享一条边。