На різдвяній вечірці \(n\) дітей, і кожна дитина принесла подарунок.

Ідея полягає в тому, що кожен отримає подарунок, який принесе хтось інший.

Скількома способами можна роздати подарунки?

Обмеження

• \(1 ≤ n ≤ 10^6\)

Формат вхідних даних

Єдиний рядок вхідних даних містить ціле число \(n\): кількість дітей.

Формат вихідних даних

Вивести кількість способів за модулем \(10^9+7\).

Приклад вхідних даних

4

Приклад вихідних даних

9