Little X's sister, Little F, is an astrologer in country X, and Little X, an enchanter, needs to assist Little F during her astrological observations.
Tonight, the stars in the sky are arranged with remarkable regularity. If we abstract the entire starry sky into a Cartesian coordinate system, there is exactly one star at every integer coordinate point, and the star where Little X and Little F are located is the origin.
Stars at the same distance from the star where Little X and Little F are located interact with each other. If we let $f(x)$ denote the number of stars at a distance of $x$ units from the star where Little X and Little F are located, then this series of stars will generate a total of $f(x)^k$ units of energy.
Little F observes that on the night of a full moon, the energy generated by stars at an integer distance from her and Little X's star becomes easy to collect. Furthermore, due to technical limitations, Little F can currently only collect energy generated by stars at a distance of no more than $N$ units from her and Little X's star. It is important to note that the star where Little X and Little F are located does not generate any energy.
Little X's task is to help Little F calculate the total amount of energy that can be collected. Since the amount of collectable energy is extremely large, Little X cannot ensure that his calculation is error-free, so he wants you to tell him the result of this value modulo a certain number $P$ to verify the correctness of his calculation.
Input
Three positive integers $N, k, P$ in a single line.
Output
A single integer $\text{Ans}$, representing the total energy modulo $P$.
Examples
Input 1
5 1 998244353
Output 1
28
Note 1
In the sample input, $k=1$. It is not difficult to see that Little X needs to calculate the number of integer points within $5$ units of the origin that are at an integer distance from the origin, modulo $998244353$.
There are $4 \times 5 = 20$ such integer points of the form $(x,0), (-x,0), (0,x), (0,-x)$. In addition to these, there are $8$ other integer points: $(3,4), (-3,4), (3,-4), (-3,-4), (4,3), (-4,3), (4,-3), (-4,-3)$, for a total of $28$ points.
Input 2
500 5 1000000000
Output 2
365511168
Input 3
142857 1 1000000009
Output 3
2481012
Input 4
998244353 998244353 998244353
Output 4
637246480
Subtasks
For all test data, it is guaranteed that $1 \leq N, k \leq 10^{11}$ and $10^8 \leq P \leq 10^9+9$.
| Test Case ID | Score | $N$ | $k$ | $P$ |
|---|---|---|---|---|
| 1 | $3$ | $\leq 1000$ | $\leq 5$ | $P$ is prime |
| 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$ is a power of $2$ |
| 14 | $1$ | $=18$ | ||
| 15 | $4$ | $\leq 10^9$ | $P$ is prime | |
| 16 | $4$ | $\leq 10^{10}$ | ||
| 17 | $4$ | |||
| 18 | $4$ | |||
| 19 | $6$ | $\leq 10^{11}$ | $\leq 10^{11}$ | No additional restrictions |
| 20 | $6$ |