题目描述

小 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$ 取模的结果。

样例 1

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