Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Cyclic Permutations

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA 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.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/26/2021 05:53:30 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|