Перестановка длины \(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 = 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\)