eolymp
bolt
Try our new interface for solving problems
Problems

Exercise (Gold)

Exercise (Gold)

Time limit 1 second
Memory limit 128 MiB

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 (1in). 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 data

One line contains n (1n10^4) and m (10^8m10^9 + 7, m is prime).

Output data

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.

Examples

Input example #1
5 1000000007
Output example #1
21
Source 2020 USACO US Open, Gold