Có n em nhỏ (1≤n≤106), mỗi em mang một món quà riêng. Phân phát mỗi món quà cho đúng một em sao cho không em nào nhận lại món quà mình đã mang.
Đếm số phép phân phát thỏa mãn và in modulo 1000000007.
Input
Một dòng chứa số nguyên n.
Output
In kết quả theo yêu cầu, lấy modulo như đã nêu trong phần mô tả.
Constraints
1≤n≤106.
Scoring
Subtask 1 (50% số điểm): các test nhỏ trong 10 test đầu của bộ dữ liệu.
Subtask 2 (50% số điểm): không có giới hạn bổ sung.
Example
Test 1
Input
1
Output
0
Giải thích: Với một phần tử, hoán vị duy nhất giữ nguyên vị trí của nó nên không thỏa yêu cầu.
Lời giải tóm tắt
Phân tích: Ký hiệu D_n là số derangement của n phần tử. Xét món quà của em 1, nó được đưa cho một em j≠1, có n-1 lựa chọn.
Phân tích: Có hai trường hợp:
Phân tích: Quà của j được đưa lại cho em 1. Khi bỏ cặp (1,j), còn D_{n-2} cách.
Phân tích: Quà của j không đưa cho em 1. Ghép vai trò vị trí của em 1 vào cấu hình còn lại cho ta song ánh với một derangement trên n-1 phần tử, có D_{n-1} cách.
Phân tích: Vì thế D_n=(n-1)(D_{n-1}+D_{n-2}), với D_0=1, D_1=0. Ta duyệt từ 2 đến n, luôn lấy modulo.
Phân tích: Có thể kiểm tra: D_2=1, D_3=2, D_4=9.
Thuật toán: Cài đặt trực tiếp công thức hoặc quy hoạch nêu trên, tiền xử lý các đại lượng tổ hợp cần thiết và chuẩn hóa mọi phép toán theo modulo của đề. Các trường hợp không khả thi được loại trước khi thực hiện phép chia modulo.
Chứng minh: Mỗi derangement được phân loại duy nhất theo người nhận quà 1 và theo việc 1 có nhận quà của người đó hay không. Hai trường hợp rời nhau và bao phủ hết. Phép bỏ/ghép ở từng trường hợp là song ánh, nên truy hồi đếm đúng không thiếu và không trùng.