A13579. 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 < 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$ .

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.