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.