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

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

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

Обмеження

• ~1 ≤ n ≤ 10^6~

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

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

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

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

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

4

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

9