The Bell number $B_n$ represents the number of ways to partition $n$ labeled balls into $n$ unlabeled sets.
For $0\le n\le N$, calculate $B_n \bmod p^k$. You only need to output
$$ \bigoplus_{n=0}^N \left((B_n \bmod p^k)+C\right) $$
where $\bigoplus$ denotes the XOR sum.
Yi'ai knows how to solve the problem for $p\le 100$, but after browsing some papers, she also learned how to solve it for $p\le 2.5\times 10^4$. In the end, she decided to only set the constraint to $p\le 100$.
Input
Input $N, p, k, C$.
Output
Output the answer.
Examples
Input 1
10 5 2 0
Output 1
18
Note 1
$$B_{0,\dots,10}= [1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975]$$
Taking modulo $25$, we get $[1, 1, 2, 5, 15, 2, 3, 2, 15, 22, 0]$, and the XOR sum is $18$.
Input 2
666 2 29 2003
Output 2
25147922
Subtasks
For $100\%$ of the data, it is guaranteed that $0\le N\le 10^6$, $p\le 100$, and $C, p^k\le 10^9$, where $p$ is a prime number.
- Test cases $1\sim 4$: $N\le 10^3$.
- Test cases $5, 6$: $N\le 5\times 10^4$.
- Test case $7$: $k=1, p\le 100$.
- Test case $8$: $k=1$.
- Test cases $9, 10$: $p^k\le 20$.
- Test cases $11\sim 18$: $p\le 100$.
- Test case $19$: $p\le 2\times 10^3$.
- Test case $20$: No special constraints.