Exercise (Gold)
Farmer John has come up with a new morning exercise routine for the cows (again)!
As before, Farmer John's n cows are standing in a line. The i-th cow from the left has label i for each i (1 ≤ i ≤ 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.
Input
One line contains n (1 ≤ n ≤ 10^4) and m (10^8 ≤ m ≤ 10^9 + 7, m is prime).
Output
A single integer.
Example
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.