CF1391C Cyclic Permutations

一个长度为 $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 \leq n \leq 10^6$）。

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

对于 $n=4$，共有 $16$ 个环状排列。$[4,2,1,3]$ 就是其中之一，它包含一个长度为 $4$ 的环：$4 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 4$。 当且仅当以下条件同时满足时，节点 $v_1, v_2, \ldots, v_k$ 构成一个简单环： - $k \geq 3$。 - 对于任意 $1 \leq i < j \leq k$，都有 $v_i \neq v_j$。 - 对于所有 $1 \leq i < k$，$v_i$ 和 $v_{i+1}$ 之间有边，且 $v_1$ 和 $v_k$ 之间有边。 由 ChatGPT 4.1 翻译