小兰想对于每个 $k=1\dots n$，求出 $k^0+k^1+\cdots+k^{m-1}$。
这道题看起来平平无奇，主要是小兰是一个讲求精shen细腻的人。她今天要对一个输入的模数 $M$ 取模。
输入格式
输入三个正整数 $n,m,M$，如题意所示。
输出格式
设关于 $k$ 的答案为 $a_k$，请你输出 $a_1 \oplus a_2 \oplus \cdots \oplus a_n$。这里 $\oplus$ 表示按位异或（xor）。
样例数据
样例 1 输入
10 4 1000
样例 1 输出
363
样例 1 解释
取模之前的答案是 $[4, 15, 40, 85, 156, 259, 400, 585, 820, 1111]$，取模之后的答案是 $[4, 15, 40, 85, 156, 259, 400, 585, 820, 111]$。
子任务
对于 $100\%$ 的数据，保证 $1\le n\le 10^7; 1\le m\le 10^{10^6}; 2\le M\le 10^{9}$。
| 测试点编号 | $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$ | 是质数 | |
| $13,14$ | $10^9$ | ||
| $15,16$ | $10^5$ | ||
| $17$ | $10^6$ | ||
| $18,19$ | $=998244353$ | ||
| $20,21$ | 是质数 | ||
| $22$ | $\mu(M)^2=1$ | ||
| $23,24$ | $=2^k$ | ||
| $25$ |
留空部分表示仅服从 $100\%$ 数据的限制。其中 $\mu(M)$ 是 Möbius 函数。
本题标准算法不需要使用 __int128，请自行斟酌。