Cyclic Permutations
Contest: Codeforces Round 663 (Div. 2)
Difficulty rating: 1500
Tags: combinatorics, dp, graphs, math

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

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

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
4

Example output:
16

Example input:
583291

Example output:
135712853

Editorial:
The answer is $$$n!-2^{n-1}$$$.
Consider an arbitrary cyclic permutation — for example, [4,2,3,1,5,6]; it contains many cycles of length $$$3$$$: $$$[1,2,3]$$$, $$$[1,3,5]$$$, $$$[3,4,5]$$$. Note that all the listed cycles contain nodes obtained from just one choice of $$$i$$$. We can generalize this to the following. If for any $$$i$$$, we make edges on both sides of it, this will create a simple cycle of length $$$3$$$. The proof is simple and is an exercise for you.
Thus, there has to at most one peak that is the element $$$n$$$– all acyclic permutations increase, then reach $$$n$$$, and, finally, decrease. These are formally called unimodal permutations, and it's easy to see that any unimodal permutation forms a tree, and, thus, contains no simple cycle  — each element, except $$$n$$$, has a uniquely defined parent.
We can construct any unimodal permutation by adding the numbers $$$n, n-1, \ldots, 1$$$ into a deque in the same order. For example, $$$[2,3,4,1]$$$ can be constructed by first pushing $$$4$$$, $$$3$$$, $$$2$$$ to the front, and, finally, $$$1$$$ at the back. Thus, for every element, except $$$n$$$, we have the choice of pushing it to the front or the back, making the total number of ways equal to $$$2^{n-1}$$$.
Time Complexity: $$$\mathcal{O}(n)$$$