C. Cyclic Permutations
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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

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

Output

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

Examples
Input
4
Output
16
Input
583291
Output
135712853
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.