Có ~n~ ông cháu tại bữa tiệc, mỗi người mang đến đúng một món quà. Tất cả cùng tổ chức một trò chơi phát quà: mỗi người sẽ nhận được đúng một món quà, và món quà đó phải do người khác mang đến.

Nói cách khác, sau khi phát xong không có ai nhận lại chính món quà mình mang đến. Hãy đếm số cách phát quà hợp lệ, chia dư cho ~10^9 + 7~.

Dữ liệu vào

Dòng đầu tiên và duy nhất chứa một số nguyên ~n~.

Kết quả

In ra số cách phát quà hợp lệ đã chia dư cho ~10^9 + 7~.

Ví dụ

Đầu vào:

3

Đầu ra:

2

Giải thích: Coi thứ tự món quà ban đầu là ~[1, 2, 3]~. Hai cách phát hợp lệ là ~[2, 3, 1]~ và ~[3, 1, 2]~. Mọi cách khác đều có ít nhất một người nhận lại quà của mình.

Giới hạn

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

Đây chính là số hoán vị không có điểm bất động (số mất thứ tự). Gọi ~D(n)~ là đáp án, ta có công thức truy hồi

~D(n) = (n - 1) \cdot \big( D(n-1) + D(n-2) \big)~

với ~D(1) = 0~ và ~D(2) = 1~.

Ý tưởng: người thứ ~n~ nhận quà của một trong ~n-1~ người còn lại, giả sử người ~j~. Nếu ~j~ nhận lại quà của người ~n~ thì ~n-2~ người còn lại tạo thành một bài toán con ~D(n-2)~; ngược lại ~j~ "thay vai" người ~n~ và ta được ~D(n-1)~.

Chú ý ~D(1) = 0~: một người thì không thể nhận quà của người khác.