小 X 的姐姐小 F 是一名 X 国的占星师，而作为附魔师的小 X 则需要在占星的过程中辅助小 F。
今夜，空中的星星排列得格外整齐，如果将整个星空抽象成一个平面直角坐标系的话，在每一个整点处，都恰好有一颗星，小 X 和小 F 所在的星就是原点。
距离小 X 和小 F 所在的星相同的星之间是会相互作用的，如果记 $f(x)$ 表示距离小 X 和小 F 所在的星 $x$ 个单位的星星的个数，那么这一系列的星将共计产生 $f(x)^k$ 点能量。
小 F 观察到，在月圆之夜，距离自己和小 X 所在的星恰好整数个单位的星产生的能量将会变得易于收集。并且，由于技术限制，小 F 暂时只能够收集距离自己和小 X 所在的星不超过 $N$ 个单位的星产生的能量。需要特别注意的是，小 X 和小 F 所在的星并不会产生能量。
小 X 要做的，就是帮助小 F 计算此时能够被收集的能量总量。由于能够收集的能量实在太过庞大，小 X 难以确保自己计算毫无失误，因此他希望你能够告诉他这个数值在对某一个数 $P$ 取模后的结果来验证他计算的正确性。
输入格式
一行三个正整数 $N,k,P$。
输出格式
一行一个整数 $\text{Ans}$，表示能量总量对 $P$ 取模的结果。
样例数据
样例输入
5 1 998244353样例输出
28样例解释
样例输入中 $k=1$，不难发现此时小 $X$ 需要计算的就是距原点 $5$ 单位内，且至原点距离为整数的整点个数，对 $998244353$ 取模的结果。
形如 $(x,0),(-x,0),(0,x),(0,-x)$ 的符合要求的整点有 $4\times 5=20$ 个；除了以上整点以外，还有 $(3,4),(-3,4),(3,-4),(-3,-4),(4,3),(-4,3),(4,-3),(-4,-3)$ 共 $8$ 个符合要求的整点，总计 $28$ 个。
样例输入
500 5 1000000000样例输出
365511168样例输入
142857 1 1000000009样例输出
2481012样例输入
998244353 998244353 998244353样例输出
637246480子任务
对于所有测试数据，保证 $1 \leq N,k \leq 10^{11},10^8 \leq P \leq 10^9+9$。
| 测试点编号 | 分值 | $N$ | $k$ | $P$ |
|---|---|---|---|---|
| 1 | $3$ | $\leq 1000$ | $\leq 5$ | $P$ 是质数 |
| 2 | $3$ | $\leq 8\times 10^3$ | ||
| 3 | $6$ | $\leq 2\times 10^5$ | ||
| 4 | $6$ | $\leq 5\times 10^5$ | ||
| 5 | $5$ | $\leq 3\times 10^6$ | ||
| 6 | $5$ | $\leq 2\times 10^7$ | ||
| 7 | $5$ | |||
| 8 | $5$ | |||
| 9 | $8$ | $\leq 2\times 10^8$ | $=1$ | |
| 10 | $8$ | |||
| 11 | $8$ | $=2$ | ||
| 12 | $8$ | |||
| 13 | $1$ | $\leq 10^9$ | $=15$ | $P$ 是 $2$ 的次幂 |
| 14 | $1$ | $=18$ | ||
| 15 | $4$ | $\leq 10^9$ | $P$ 是质数 | |
| 16 | $4$ | $\leq 10^{10}$ | ||
| 17 | $4$ | |||
| 18 | $4$ | |||
| 19 | $6$ | $\leq 10^{11}$ | $\leq 10^{11}$ | 没有额外的限制 |
| 20 | $6$ |