Mô tả và yêu cầu

Bài tập (Exercise.*)

Farmer John lại nghĩ ra một bài tập buổi sáng mới cho đàn bò!
Cũng như mọi khi, đàn bò của Farmer John gồm N con bò (1 ≤ 𝑁 ≤ 104 ) đứng thành

một hàng. Con bò thứ i từ bên trái có nhãn là i.
Ông yêu cầu đàn bò lặp lại bước sau đây cho đến khi chúng trở lại đúng thứ tự ban đầu:
- Cho một hoán vị A gồm N phần tử, mỗi bước các con bò sẽ đổi vị trí sao cho con bò
đang ở vị trí thứ i sẽ chuyển đến vị trí 𝐴𝑖 (theo thứ tự từ trái sang phải).

Ví dụ

- Nếu A = (1, 2, 3, 4, 5), thì thứ tự không đổi → cần 0 bước.
- Nếu A = (2, 3, 1, 5, 4), thì các bước đổi chỗ lần lượt như sau:
                                            0 𝑏ướ𝑐: (1,   2, 3, 4, 5)
                                            1 𝑏ướ𝑐: (2,   3, 1, 5, 4)
                                            2 𝑏ướ𝑐: (3,   1, 2, 4, 5)
                                            3 𝑏ướ𝑐: (1,   2, 3, 5, 4)
                                            4 𝑏ướ𝑐: (2,   3, 1, 4, 5)
                                            5 𝑏ướ𝑐: (3,   1, 2, 5, 4)
                                            6 𝑏ướ𝑐: (1,   2, 3, 4, 5)
→ Như vậy, cần đúng 6 bước để trở lại trạng thái ban đầu.
Yêu cầu: Tìm tổng của tất cả các số nguyên dương K sao cho tồn tại ít nhất một hoán vị
độ dài N mà cần đúng K bước để trở lại thứ tự ban đầu.
Do kết quả có thể rất lớn, in ra tổng đó modulo M, với:
- 108   ≤   𝑀   ≤   109   +   7

- M là số nguyên tố.
Dữ liệu vào:
     Gồm 1 dòng chứa 2 số nguyên N và M.
Dữ liệu ra:
     Một số nguyên duy nhất là kết quả cần tìm, tính theo modulo M.

Ví dụ:
                           INPUT                                          OUTPUT
         5 1000000007                                    21

Giải thích:
Có các hoán vị khiến đàn bò quay lại sau đúng 1, 2, 3, 4, 5 và 6 bước.
Tổng là: 1 + 2 + 3 + 4 + 5 + 6 = 21
Subtask:
- Các test 2–5: 𝑁     ≤  102

- Các test 6–10: Không có ràng buộc bổ sung