小兰は、各 $k=1\dots n$ に対して $k^0+k^1+\cdots+k^{m-1}$ を求めたいと考えています。
この問題は一見平凡に見えますが、小蘭は精神的な繊細さを大切にする人物です。彼女は今日、入力された法 $M$ で割った余りを求めることにしました。
入力
3つの正整数 $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)$ はメビウス関数です。
本問題の標準的なアルゴリズムでは __int128 を使用する必要はありません。各自で判断してください。