CF1391C.Cyclic Permutations

A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

Consider a permutation $p$ of length $n$, we build a graph of size $n$ using it as follows:

• For every $1 \leq i \leq n$, find the largest $j$ such that $1 \leq j \lt i$ and $p_j \gt p_i$, and add an undirected edge between node $i$ and node $j$
• For every $1 \leq i \leq n$, find the smallest $j$ such that $i \lt j \leq n$ and $p_j \gt p_i$, and add an undirected edge between node $i$ and node $j$

In cases where no such $j$ exists, we make no edges. Also, note that we make edges between the corresponding indices, not the values at those indices.

For clarity, consider as an example $n = 4$, and $p = [3,1,4,2]$; here, the edges of the graph are $(1,3),(2,1),(2,3),(4,3)$.

A permutation $p$ is cyclic if the graph built using $p$ has at least one simple cycle.

Given $n$, find the number of cyclic permutations of length $n$. Since the number may be very large, output it modulo $10^9+7$.

Please refer to the Notes section for the formal definition of a simple cycle

长度为 $n$ 的排列是指由 $1$ 到 $n$ 中互不相同的 $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$ 是环状的（cyclic）。

给定 $n$，求长度为 $n$ 的环状排列的个数。由于答案可能非常大，请输出其对 $10^9+7$ 取模的结果。

有关简单环的严格定义，请参见“注释”（Notes）部分。

The first and only line contains a single integer $n$ ($3 \le n \le 10^6$).

第一行且唯一一行包含一个整数 $n$（$3 \le n \le 10^6$）。

Output a single integer $0 \leq x \lt 10^9+7$, the number of cyclic permutations of length $n$ modulo $10^9+7$.

输出一个整数 $0 \leq x \lt 10^9+7$，表示长度为 $n$ 的循环排列的个数对 $10^9+7$ 取模的结果。

There are $16$ cyclic permutations for $n = 4$. $[4,2,1,3]$ is one such permutation, having a cycle of length four: $4 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 4$.

Nodes $v_1$, $v_2$, $\ldots$, $v_k$ form a simple cycle if the following conditions hold:

• $k \geq 3$.
• $v_i \neq v_j$ for any pair of indices $i$ and $j$. ($1 \leq i \lt j \leq k$)
• $v_i$ and $v_{i+1}$ share an edge for all $i$ ($1 \leq i \lt k$), and $v_1$ and $v_k$ share an edge.

当 $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$；
• 对任意下标对 $i$ 和 $j$（其中 $1 \leq i \lt j \leq k$），均有 $v_i \neq v_j$；
• 对所有 $i$（其中 $1 \leq i \lt k$），$v_i$ 与 $v_{i+1}$ 相邻（即二者之间存在一条边），且 $v_1$ 与 $v_k$ 相邻。