Farmer John's Permutation Order Sum

Farmer John has come up with a new morning exercise for his cows! As before, his N cows are standing in a line, numbered from 1 to N from left to right. Farmer John gives them a permutation A of length N. In one step, the cows rearrange themselves so that the cow that was in the i-th position moves to the A_i-th position. They repeatedly perform this step until they return to the original order. For example, if N = 5 and A = (2,3,1,5,4), the orders after each step are:

Step 0: (1,2,3,4,5)
Step 1: (3,1,2,5,4)
Step 2: (2,3,1,4,5)
Step 3: (1,2,3,5,4)
Step 4: (3,1,2,4,5)
Step 5: (2,3,1,5,4)
Step 6: (1,2,3,4,5)

In this process, the number of steps required for the cows to return to the starting order is exactly the order of the permutation A, which is the least common multiple (lcm) of the cycle lengths of A. It can be shown that for any permutation of N elements, the order is of the form \[ K = \mathrm{lcm}(l_1, l_2, \dots, l_m), \] where the cycle lengths l₁, l₂, ..., l_m are positive integers satisfying \[ l_1 + l_2 + \cdots + l_m = N. \]

Your task is to compute the sum of all positive integers K for which there exists a permutation of length N whose order is exactly K. It turns out that the set of possible orders is exactly the set of all divisors of \[ L = \mathrm{lcm}(1, 2, \dots, N) = \prod_{p \le N} p^{a_p}, \quad \text{where } a_p = \max\{a \mid p^a \le N\}. \] Thus, the answer is the sum of all divisors of L modulo M (where M is a prime number with \(10^8 \le M \le 10^9+7\)).

In summary, given two integers N and M, compute

[ \text{Answer} = \left( \sum_{d \mid L} d \right) \bmod M, \quad \text{with } L = \prod_{p \le N} p^{\lfloor \log_p N \rfloor}. ]

Note: You may assume that a permutation achieving any divisor of L as its order exists.

inputFormat

The input consists of a single line containing two integers N and M separated by a space, where 1 \(\le\) N, and M is a prime number satisfying \(10^8 \le M \le 10^9+7\).

Example:

5 100000007

outputFormat

Output a single integer, the sum of all possible orders of a permutation of length N (i.e. the sum of all divisors of \(L=\mathrm{lcm}(1,2,\dots,N)\)) modulo M.

Example Output:

168

sample

1 100000007

1