C. Циклические перестановки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Перестановка длины $$$n$$$  — это массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$  — это перестановка, но $$$[1,2,2]$$$  — это не перестановка ($$$2$$$ встречается дважды в массиве), а $$$[1,3,4]$$$ также не является перестановкой ($$$n=3$$$, но в массиве встречается $$$4$$$).

Рассмотрим перестановку $$$p$$$ длины $$$n$$$. Построим граф на $$$n$$$ вершинах, используя перестановку следующим образом:

  • Для каждого $$$1 \leq i \leq n$$$ найдите наибольшее значение $$$j$$$, для которого $$$1 \leq j < i$$$ и $$$p_j > p_i$$$, и добавьте неориентированное ребро между вершинами $$$i$$$ и $$$j$$$.
  • Для каждого $$$1 \leq i \leq n$$$ найдите наименьшее значение $$$j$$$, для которого $$$i < j \leq n$$$ и $$$p_j > p_i$$$, и добавьте неориентированное ребро между вершинами $$$i$$$ и $$$j$$$

В тех случаях, когда таких $$$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$$$ образуют простой цикл, если выполняются следующие условия:

  • $$$k \geq 3$$$.
  • $$$v_i \neq v_j$$$ для любой пары индексов $$$i$$$ и $$$j$$$. ($$$1 \leq i < j \leq k$$$)
  • Между $$$v_i$$$ и $$$v_{i+1}$$$ есть ребро для всех $$$i$$$ ($$$1 \leq i < k$$$), как и между $$$v_1$$$ и $$$v_k$$$