Problem Description

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).

Input Format

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

Output Format

Output one integer.

5 1000000007

21

Hint

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