Задачі
ПерестановочкИ
ПерестановочкИ
Для перестановки $p$ чисел від $1$ до $n$, визначимо $f(p)$ наступним чином: для кожної пари чисел $(i, j)$ з $1 \le i \le j \le n$, порахуємо пару $(min, max)$, де $min$ --- найменше число серед чисел $a_i, a_{i+1}, \ldots, a_j$, а $max$ --- найбільше з них. Тоді $f(p)$ рівна кількості різних пар серед всіх $\frac{n(n+1)}{2}$ пар.
Наприклад розглянемо перестановку $(1, 3, 2)$.
\begin{itemize}
\item
Для пари $(1, 1)$, $(min, max) = (1, 1)$
\item
Для пари $(1, 2)$, $(min, max) = (1, 3)$
\item
Для пари $(1, 3)$, $(min, max) = (1, 3)$
\item
Для пари $(2, 2)$, $(min, max) = (3, 3)$
\item
Для пари $(2, 3)$, $(min, max) = (2, 3)$
\item
Для пари $(3, 3)$, $(min, max) = (2, 2)$
\end{itemize}
Всього $5$ різних пар, тому $f((1, 3, 2)) = 5$.
Знайдіть суму $f(p)$ по всім перестановкам $p$ довжини $n$, за модулем $10^9 + 7$.
\InputFile
Єдиний рядок вхідних даних містить єдине число $n$ ($1 \le n \le 2\cdot 10^5$).
\OutputFile
Виведіть суму $f(p)$ по всім перестановкам $p$ довжини $n$, за модулем $10^9 + 7$.
Вхідні дані #1
1
Вихідні дані #1
1
Вхідні дані #2
2
Вихідні дані #2
6
Вхідні дані #3
3
Вихідні дані #3
32
Вхідні дані #4
228
Вихідні дані #4
384127128