Bell 数 $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$ 表示异或和。
忆艾自己会 $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
子任务
对于 $100\%$ 的数据，保证 $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$：无特殊限制。