Problem Background

This is an important prerequisite for the Zhou Ge sieve and Min_25 sieve.

Problem Description

Let $S(n)$ be the sum of the $k$-th powers of primes less than or equal to $n$.

Given $N$, compute the value of the following expression:

$$\sum_{i=1}^{\lfloor\sqrt{N}\rfloor} i^2 S \!\left( \left\lfloor \frac{N}{i} \right\rfloor \right)$$

All results should be taken modulo a given prime number $p$.

Input Format

A single line containing three integers $N, k, p$, separated by spaces.

Output Format

A single line containing an integer representing the result of the computation.

Sample Input and Output

Sample Input #1

10 3 1000000007

Sample Output #1

1458

Sample Input #2

100000 0 1000000007

Sample Output #2

941229402

Sample Input #3

100000 10 1000000007

Sample Output #3

446053671

Notes

Sample Explanation:

$S \!\left( \left\lfloor \frac{N}{1} \right\rfloor \right) = S(10) = 2^3 + 3^3 + 5^3 + 7^3 = 503$.

$S \!\left( \left\lfloor \frac{N}{2} \right\rfloor \right) = S(5) = 2^3 + 3^3 + 5^3 = 160$.

$S \!\left( \left\lfloor \frac{N}{3} \right\rfloor \right) = S(3) = 2^3 + 3^3 = 35$.

$1^2 S \!\left( \left\lfloor \frac{N}{1} \right\rfloor \right) + 2^2 S \!\left( \left\lfloor \frac{N}{2} \right\rfloor \right) + 3^2 S \!\left( \left\lfloor \frac{N}{3} \right\rfloor \right) = 503 + 640 + 315 = 1458$.

For $100\%$ of the data, $0 \le k \le 10$, $1 \le N \le 4\times {10}^{10}$, ${10}^9 < p < 1.01 \times {10}^9$.

见题面 Input 部分

见题面 Output 部分