Codeforces Round 663 (Div. 2) |
---|
Закончено |
Перестановка длины $$$n$$$ — это массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — это перестановка, но $$$[1,2,2]$$$ — это не перестановка ($$$2$$$ встречается дважды в массиве), а $$$[1,3,4]$$$ также не является перестановкой ($$$n=3$$$, но в массиве встречается $$$4$$$).
Рассмотрим перестановку $$$p$$$ длины $$$n$$$. Построим граф на $$$n$$$ вершинах, используя перестановку следующим образом:
В тех случаях, когда таких $$$j$$$ не существует, мы не добавляем ребер. Также обратите внимание, что мы проводим ребра между соответствующими индексами, а не значениями в этих индексах.
Например, рассмотрим случай $$$n = 4$$$ и $$$p = [3,1,4,2]$$$; здесь ребрами графа являются $$$(1,3),(2,1),(2,3),(4,3)$$$.
Перестановка $$$p$$$ является циклической, если граф, построенный с использованием $$$p$$$, имеет хотя бы один простой цикл.
Для данного $$$n$$$, найдите число циклических перестановок длины $$$n$$$. Поскольку число может быть очень большим, выведите его по модулю $$$10^9+7$$$.
Пожалуйста, обратитесь к разделу Примечания для формального определения простого цикла.
Первая и единственная строка содержит одно целое число $$$n$$$ ($$$3 \le n \le 10^6$$$).
Выведите единственное целое число $$$0 \leq x < 10^9+7$$$, количество циклических перестановок длины $$$n$$$ по модулю $$$10^9+7$$$.
4
16
583291
135712853
Для $$$n = 4$$$ существует $$$16$$$ циклических перестановок. $$$[4,2,1,3]$$$ — одна из таких перестановок, она содержит цикл длины четыре: $$$4 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 4$$$.
Вершины $$$v_1$$$, $$$v_2$$$, $$$\ldots$$$, $$$v_k$$$ образуют простой цикл, если выполняются следующие условия:
Название |
---|