Юниорская олимпиада по информатике 2022 года за 8 класс | Казахстанские олимпиады

Задача A. Хулиган-староста

В классе учится $n$ учеников. В школах у каждого школьника есть свое место. Ученик под номером $i$ сидит за $i$-той партой. Сегодня староста класса хочет похулиганить. Она решила посадит учеников так чтобы ни один ученик не сидел на своем месте. Она просит вас найти количество способов это сделать по модулю $10^9 + 7$. Например, если в классе 3 ученика тогда всего есть два способа как их можно посадить $([2 3 1], [3 1 2])$.

Формат входного файла

Дается $n (1 \leq n \leq 1000000)$ - количество учеников в классе.

Формат выходного файла

Вывести количество способов по модулю $10^9 + 7$.

Система оценки

Примеры

Входные данные

1

Выходные данные

0

Входные данные

5

Выходные данные

44