题目背景

这是洲阁筛和 Min_25 筛的重要前置知识。

学到这里就不讲定义了。

题目描述

设 $S(n)$ 为 $n$ 以内质数的 $k$ 次方和。

给出 $N$，求下列式子的值。

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

所有结果对给定的质数 $p$ 取模。

输入格式

一行三个整数 $N,k,p$，之间用空格隔开。

输出格式

一行一个整数，代表计算的结果。

10 3 1000000007

1458

100000 0 1000000007

941229402

100000 10 1000000007

446053671

提示

样例解释 :

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

测试点编号	$N \le$	$k \le$	时限
$1\sim 3$	$10^6$	$10$	$1\texttt s$
$4\sim 7$	$4\times {10}^{10}$	$0$	$3\texttt s$
$8\sim 12$		$10$

对于 $100\%$ 的数据，$0 \le k \le 10$，$1 \le N \le 4\times {10}^{10}$，${10}^9 < p < 1.01 \times {10}^9$。