Codeforces Round 663 (Div. 2) |
---|
Finished |
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:
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$$$.
4
16
583291
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:
Name |
---|