Exercise

문제

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

As before, Farmer John's $NN$ cows ($1\le N\le {10}^{4}1\backslash le\; N\backslash le\; 10^4$) are standing in a line. The $ii$-th cow from the left has label $ii$ for each $1\le i\le N1\backslash le\; i\backslash 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 $AA$ of length $NN$, the cows change their order such that the $ii$-th cow from the left before the change is $A_{i}A\_i$-th from the left after the change.

For example, if $A=(1,2,3,4,5)A=(1,2,3,4,5)$ then the cows perform one step. If $A=(2,3,1,5,4)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,2,3,4,5)$
• 1 step: $(3,1,2,5,4)(3,1,2,5,4)$
• 2 steps: $(2,3,1,4,5)(2,3,1,4,5)$
• 3 steps: $(1,2,3,5,4)(1,2,3,5,4)$
• 4 steps: $(3,1,2,4,5)(3,1,2,4,5)$
• 5 steps: $(2,3,1,5,4)(2,3,1,5,4)$
• 6 steps: $(1,2,3,4,5)(1,2,3,4,5)$

Find the sum of all positive integers $KK$ such that there exists a permutation of length $NN$ that requires the cows to take exactly $KK$ steps.

As this number may be very large, output the answer modulo $MM$ (${10}^8\le M\le {10}^9+710^8\backslash le\; M\backslash le\; 10^9+7$, $MM$ is prime).

입력

The first line contains $NN$ and $MM$.

출력

A single integer.

힌트

There exist permutations that cause the cows to take $11$, $22$, $33$, $44$, $55$, and $66$ steps. Thus, the answer is $1+2+3+4+5+6=211+2+3+4+5+6=21$.

5 1000000007

21