eolymp
Competitions

2021-2022 ICPC, SEERC, 1/8 Final

ПерестановочкИ

Для перестановки $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$.
Time limit 1 second
Memory limit 256 MiB
Input example #1
1
Output example #1
1
Input example #2
2
Output example #2
6
Input example #3
3
Output example #3
32
Input example #4
228
Output example #4
384127128
Author Anton Trygub