For each $k=1\dots n$, calculate $k^0+k^1+\cdots+k^{m-1}$.
This problem seems straightforward, but Xiao Lan is a person who pays great attention to detail. Today, she wants to perform the calculation modulo $M$.
Input Format
The input contains three positive integers $n, m, M$, as described in the problem.
Output Format
Let $a_k$ be the answer for a given $k$. Output $a_1 \oplus a_2 \oplus \cdots \oplus a_n$, where $\oplus$ denotes the bitwise XOR operation.
Examples
Input 1
10 4 1000
Output 1
363
Note
The answers before taking the modulo are $[4, 15, 40, 85, 156, 259, 400, 585, 820, 1111]$, and the answers after taking the modulo are $[4, 15, 40, 85, 156, 259, 400, 585, 820, 111]$.
Subtasks
For $100\%$ of the data, it is guaranteed that $1\le n\le 10^7; 1\le m\le 10^{10^6}; 2\le M\le 10^{9}$.
| Test Case ID | $n\le$ | $m\le$ | $M$ |
|---|---|---|---|
| $1,2$ | $10^3$ | $10^3$ | |
| $3\sim 5$ | $10^5$ | $10^9$ | |
| $6\sim 8$ | $10^6$ | $10^9$ | |
| $9,10$ | $10^9$ | $=998244353$ | |
| $11,12$ | $10^9$ | Prime | |
| $13,14$ | $10^9$ | ||
| $15,16$ | $10^5$ | ||
| $17$ | $10^6$ | ||
| $18,19$ | $=998244353$ | ||
| $20,21$ | Prime | ||
| $22$ | $\mu(M)^2=1$ | ||
| $23,24$ | $=2^k$ | ||
| $25$ |
Empty cells indicate that only the $100\%$ data constraints apply. $\mu(M)$ is the Möbius function.
The standard algorithm for this problem does not require the use of __int128; please consider this carefully.