P6280 [USACO20OPEN] Exercise G

Farmer John has (again) come up with a new morning exercise plan for his cows. As before, Farmer John’s $N$ cows stand in a line. For each $i$ with $1 \le i \le N$, the $i$-th cow from left to right has ID $i$. He tells them to repeat the following step until the cows return to the same order as they started. Given a permutation $A$ of length $N$, the cows change their order so that the cow that was $i$-th from left to right before the change becomes the $A_i$-th from left to right after the change. For example, if $A = (1,2,3,4,5)$, then the cows perform a total of one step. If $A = (2,3,1,5,4)$, then the cows perform a total of six steps. After each step, the order of the cows from left to right is as follows: $0$ steps: $(1,2,3,4,5)$ $1$ step: $(3,1,2,5,4)$ $2$ steps: $(2,3,1,4,5)$ $3$ steps: $(1,2,3,5,4)$ $4$ steps: $(3,1,2,4,5)$ $5$ steps: $(2,3,1,5,4)$ $6$ steps: $(1,2,3,4,5)$ **Find the sum of all positive integers $K$ such that there exists a permutation of length $N$ for which the cows need exactly $K$ steps.** Since this number may be very large, output the remainder of the answer modulo $M$ ($10^8 \le M \le 10^9 + 7$, and $M$ is prime).

The first line of input contains $N$ and $M$.

Output one integer.

#### Sample Explanation: There exist permutations such that the cows need $1$, $2$, $3$, $4$, $5$, and $6$ steps. Therefore, the answer is $1 + 2 + 3 + 4 + 5 + 6 = 21$. ----- For $100\%$ of the testdata, $1 \le N \le 10^4$. There are $10$ test points. Test point $1$ is the sample, and the rest have the following properties: Test points $2$ to $5$ satisfy $N \le 10^2$. Test points $6$ to $10$ have no additional constraints. ----- Problem setter: Benjamin Qi Translated by ChatGPT 5