Có ~n~ đứa trẻ trong một bữa tiệc Giáng sinh, và mỗi đứa đều mang theo một món quà. Ý tưởng là mỗi người sẽ nhận được một món quà do người khác mang đến.

Có bao nhiêu cách phân phối quà?

Dữ liệu vào

Dòng duy nhất chứa số nguyên ~n~: số lượng trẻ em.

Kết quả

In ra số cách modulo ~10^9+7~.

Giới hạn

• ~1 \le n \le 10^6~

Ví dụ

Dữ liệu vào:

4

Kết quả:

9