Cyclic Permutations

题意翻译

给定一个长度为 $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)$ 。 **题目要求：给定 $n$ ，求出有几个长度为 $n$ 的排列，使得该排列按以上方法构造的图中有环。答案对 $10^9+7$ 取模。**

题目描述

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 < i $ and $ p_j > 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 < j \leq n $ and $ p_j > 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

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #1

4

输出样例 #1

16

输入样例 #2

583291

输出样例 #2

135712853

说明

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 < j \leq k $ ) - $ v_i $ and $ v_{i+1} $ share an edge for all $ i $ ( $ 1 \leq i < k $ ), and $ v_1 $ and $ v_k $ share an edge.