시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 144 | 83 | 71 | 53.788% |
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.
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:
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).
The first line contains $N$ and $M$.
A single integer.
5 1000000007
21
There exist permutations that cause the cows to take $1$, $2$, $3$, $4$, $5$, and $6$ steps. Thus, the answer is $1+2+3+4+5+6=21$.