ベル数 $B_n$ は、$n$ 個のラベル付きの球を $n$ 個の順序のない集合に分割する方法の数である。

$0\le n\le N$ に対して、$B_n \bmod p^k$ を計算せよ。以下の値を計算して出力すること。

$$ \bigoplus_{n=0}^N \left((B_n \bmod p^k)+C\right) $$

ここで、$\bigoplus$ は排他的論理和（XOR）を表す。

Yi Ai 自身は $p\le 100$ の場合の解法を知っているが、論文を調べた結果 $p\le 2.5\times 10^4$ の場合も解けるようになった。しかし、最終的には $p\le 100$ の場合のみを出題することにした。

入力

$N, p, k, C$ が与えられる。

出力

答えを出力せよ。

入出力例

入力 1

10 5 2 0

出力 1

18

注記 1

$$B_{0,\dots,10}= [1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975]$$

これらを $25$ で割った余りは $[1, 1, 2, 5, 15, 2, 3, 2, 15, 22, 0]$ となり、これらの排他的論理和は $18$ である。

入力 2

666 2 29 2003

出力 2

25147922

小課題

すべてのデータにおいて、$0\le N\le 10^6$、$p\le 100$、$C, p^k\le 10^9$ を満たす。ここで $p$ は素数である。

• テストケース $1\sim 4$: $N\le 10^3$ を保証する。
• テストケース $5, 6$: $N\le 5\times 10^4$ を保証する。
• テストケース $7$: $k=1, p\le 100$ を保証する。
• テストケース $8$: $k=1$ を保証する。
• テストケース $9, 10$: $p^k\le 20$ を保証する。
• テストケース $11\sim 18$: $p\le 100$ を保証する。
• テストケース $19$: $p\le 2\times 10^3$ を保証する。
• テストケース $20$: 特殊な制約はない。