Для перестановки чисел від до , визначимо наступним чином: для кожної пари чисел з , порахуємо пару , де — найменше число серед чисел , а — найбільше з них. Тоді рівна кількості різних пар серед всіх пар.
Наприклад розглянемо перестановку .
Для пари ,
Для пари ,
Для пари ,
Для пари ,
Для пари ,
Для пари ,
Всього різних пар, тому .
Знайдіть суму по всім перестановкам довжини , за модулем .
Єдиний рядок вхідних даних містить єдине число ().
Виведіть суму по всім перестановкам довжини , за модулем .