Sum of powers - 2#11785
Sign in

Sum of powers - 2

2 seconds
128 megabytes
Easy

Let be the smallest divisor of greater than . For example, f(12) = 2, f(13) = 13.

Let be the number of divisors of . For example, d(18) = 6, since has divisors: 1, 2, 3, 6, 9, 18.

Find the value of the following sum:

S = \left( \sum_{i = 2}^n d(i)^{f(i)}\right) \mod m

where is a given number.

Input

Two positive integers n~(2 \le n \le 10^7) and m~(m \le 10^9).

Output

Print the value of the sum .

Examples

For n = 5, the answer is S = 2^2 + 2^3 + 3^2 + 2^5 = 53.

Example 1

Loading
Loading