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 Ai-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 ≤ 104) and m (108 ≤ m ≤ 109 + 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.