Trong một hội thảo nâng cao chất lượng giảng dạy các trường THPT, có ~n~ đại biểu tham dự. Mỗi đại biểu mang theo một tài liệu là đề tài nghiên cứu của mình.

Để thẩm định chất lượng các tài liệu một cách khách quan, ban tổ chức thu lại toàn bộ ~n~ tài liệu này và đánh số từ ~1~ đến ~n~ tương ứng với các đại biểu. Sau đó, các tài liệu được phát lại cho ~n~ đại biểu, mỗi đại biểu nhận một tài liệu, sao cho không có bất kỳ đại biểu nào nhận lại tài liệu của chính mình.

Yêu cầu: Hãy đếm tất cả số cách ban tổ chức có thể phân phát tài liệu thỏa mãn điều kiện trên.

Hai cách phân phát được coi là khác nhau nếu tồn tại ít nhất một đại biểu nhận được hai tài liệu khác nhau trong hai cách đó. Vì số cách phân phát có thể rất lớn nên kết quả được lấy là phần dư của số cách phân phát khi chia cho ~10^9 + 7~.

Input

Chứa một số nguyên ~n~ ~(1 \le n \le 10^6)~ là số lượng đại biểu.

Output

Một số nguyên duy nhất là kết quả của bài toán.

Scoring

Sample Input 1

2

Sample Output 1

1

Sample Input 2

3

Sample Output 2

2

Sample Input 3

5

Sample Output 3

44

Notes

Trong ví dụ thứ nhất, có ~1~ cách phân phát: ~(2, 1)~.

Trong ví dụ thứ hai, có ~2~ cách phân phát: ~(2, 3, 1)~ và ~(3, 1, 2)~.