ПерестановочкИ
ПерестановочкИ
Для перестановки 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).
Для пари (1, 1), (min, max) = (1, 1)
Для пари (1, 2), (min, max) = (1, 3)
Для пари (1, 3), (min, max) = (1, 3)
Для пари (2, 2), (min, max) = (3, 3)
Для пари (2, 3), (min, max) = (2, 3)
Для пари (3, 3), (min, max) = (2, 2)
Всього 5 різних пар, тому f((1, 3, 2)) = 5.
Знайдіть суму f(p) по всім перестановкам p довжини n, за модулем 10^9 + 7.
Input data
Єдиний рядок вхідних даних містить єдине число n (1 \le n \le 2\cdot 10^5).
Output data
Виведіть суму f(p) по всім перестановкам p довжини n, за модулем 10^9 + 7.
Examples
1
1
2
6
3
32
228
384127128