eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 1 second
Memory limit 256 MiB

Для перестановки 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

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