Farmer John has come up with a new morning exercise routine for the cows
(again)!

As before, Farmer John's \(N\) cows (\(1\le N\le 10^4\)) are standing in a line.
The \(i\)-th cow from the left has label \(i\) for each \(1\le i\le N\). He tells them
to repeat the following step until the cows are in the same order as when they
started.

• Given a permutation \(A\) of length \(N\), the cows change their order such that the \(i\)-th cow from the left before the change is \(A_i\)-th from the left after the change.

For example, if \(A=(1,2,3,4,5)\) then the cows perform one step. If
\(A=(2,3,1,5,4)\), then the cows perform six steps. The order of the cows from
left to right after each step 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\) that requires the cows to take exactly \(K\) steps.

As this number may be very large, output the answer modulo \(M\)
(\(10^8\le M\le 10^9+7\), \(M\) is prime).

Problem credits: Benjamin Qi

SCORING

• Test cases 2-5 satisfy \(N\le 10^2\).
• Test cases 6-10 satisfy no additional constraints.

Problem credits: Benjamin Qi

The first line contains \(N\) and \(M\).

A single integer.

riseoj 작성

출처 올림피아드 > USACO > 2019-2020 > US Open > Gold