Background

This is important prerequisite knowledge for the Zhouge sieve and the Min_25 sieve.

Problem Description

Let $S(n)$ be the sum of the $k$-th powers of all primes not exceeding $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 are taken modulo the given prime $p$.

Input Format

One line contains three integers $N, k, p$, separated by spaces.

Output Format

Output one integer on one line, representing the computed result.

10 3 1000000007

1458

100000 0 1000000007

941229402

100000 10 1000000007

446053671

Hint

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$.

Constraints

Test Point ID	$N \le$	$k \le$	Time Limit
$1\sim 3$	$10^6$	$10$	$1\texttt s$
$4\sim 7$	$4\times {10}^{10}$	$0$	$3\texttt s$
$8\sim 12$		$10$

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

Translated by ChatGPT 5