质数前缀统计
题目背景
这是洲阁筛和 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$，之间用空格隔开。
输出格式
一行一个整数，代表计算的结果。
输入输出样例
输入样例 #1
10 3 1000000007输出样例 #1
1458输入样例 #2
100000 0 1000000007输出样例 #2
941229402输入样例 #3
100000 10 1000000007输出样例 #3
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$ | $4\times {10}^{10}$ | $10$ | $3\texttt s$ |
对于 $100\%$ 的数据，$0 \le k \le 10$，$1 \le N \le 4\times {10}^{10}$，${10}^9 < p < 1.01 \times {10}^9$。