Nông dân John lại nghĩ ra một bài tập thể dục buổi sáng mới cho những con bò!

Như trước đây, \(N\) con bò của Nông dân John (\(1 \leq N \leq 10^4\)) đang đứng thành một hàng. Con bò thứ \(i\) từ bên trái mang nhãn \(i\) với mỗi \(1 \leq i \leq N\). Ông yêu cầu chúng lặp lại bước sau cho đến khi những con bò trở về đúng thứ tự ban đầu:

• Cho một hoán vị \(A\) độ dài \(N\), những con bò thay đổi thứ tự sao cho con bò đứng thứ \(i\) từ bên trái trước khi thay đổi sẽ đứng thứ \(A_i\) từ bên trái sau khi thay đổi.

Ví dụ, nếu \(A=(1,2,3,4,5)\) thì những con bò thực hiện một bước. Nếu \(A=(2,3,1,5,4)\) thì những con bò thực hiện sáu bước. Thứ tự của những con bò từ trái sang phải sau mỗi bước như sau:

• 0 bước: \((1,2,3,4,5)\)
• 1 bước: \((3,1,2,5,4)\)
• 2 bước: \((2,3,1,4,5)\)
• 3 bước: \((1,2,3,5,4)\)
• 4 bước: \((3,1,2,4,5)\)
• 5 bước: \((2,3,1,5,4)\)
• 6 bước: \((1,2,3,4,5)\)

Tìm tổng của tất cả các số nguyên dương \(K\) sao cho tồn tại một hoán vị độ dài \(N\) khiến những con bò phải thực hiện đúng \(K\) bước.

Vì số này có thể rất lớn, hãy in đáp án theo modulo \(M\) (\(10^8 \leq M \leq 10^9+7\), \(M\) là số nguyên tố).

Dữ liệu vào

Tệp exercise.in:

Dòng đầu tiên chứa \(N\) và \(M\).

Dữ liệu ra

Tệp exercise.out:

In một số nguyên duy nhất.

Phân nhóm

• Các test 2–5 thỏa mãn \(N \leq 10^2\).
• Các test 6–10 không có ràng buộc bổ sung.

Ví dụ

5 1000000007

21

Nguồn

USACO 2020 US Open Contest, Gold — Exercise

Tác giả bài: Benjamin Qi.