定义 $f(j)\ \equiv\ \sum_{i=0}^{n-1}\ C_{i\cdot d}^{j}\ {\pmod M},\ 0\ \leq\ f(j)\ <\ M$，其中 $n,\ d,\ M$ 为给定值。
现在给定 $m$，输出 $f(0)\ \mathrm{xor}\ f(1)\ \mathrm{xor}\ f(2)\ \mathrm{xor}\ \cdots\ \mathrm{xor}\ f(m - 1)$ 的值。
其中 $C_{n}^{m}$ 为组合数 $n$ 选 $m$，即 $C_{n}^{m}\ =\ \displaystyle \begin{cases}\frac{n!}{m!\cdot (n-m)!}&, 0\leq m\leq n \cr 0&, \text{otherwise}\end{cases}$。$\mathrm{xor}$ 表示异或和。
输入格式
一行四个整数 $n,\ m,\ d,\ M$，由空格隔开。
输出格式
一行一个整数表示答案。
样例数据
样例输入
3 2 3 998244353样例输出
10样例解释
$f(0)\ \equiv\ C_0^0\ +\ C_3^0\ +\ C_6^0\ \equiv\ 1\ +\ 1\ +\ 1\ \equiv\ 3 \pmod{998244353}$
$f(1)\ \equiv\ C_0^1\ +\ C_3^1\ +\ C_6^1\ \equiv\ 0\ +\ 3\ +\ 6\ \equiv\ 9 \pmod{998244353}$
$f(0)\ \mathrm{xor}\ f(1)\ =\ 3\ \mathrm{xor}\ 9\ =\ 10$
子任务
本题采用捆绑测试。
对于所有测试包均满足 $1\ \leq\ d\ \leq\ 100,\ 1\ \leq\ m\cdot d\ \leq\ 3\times 10^6,\ 1\ \leq\ n\cdot d\ \leq\ 10^9,\ 10^8\ \leq\ M\ \leq\ 10^9$。
| 测试包编号 | 测试包分值 | 其它约定 |
|---|---|---|
| $1$ | $4$ | $n\cdot d,\ m\ \leq\ 2000$ |
| $2$ | $10$ | $m\ \leq\ 400$ |
| $3$ | $6$ | $m\ \leq\ 8000,\ M\ =\ 998244353$ |
| $4$ | $6 $ | $m\ \leq\ 8000$ |
| $5$ | $7$ | $d\ =\ 1$ |
| $6$ | $22$ | $\gcd(d,\ M)\ =\ 1$ |
| $7 $ | $7$ | $d\ =\ 2$ |
| $8$ | $7$ | $d\ =\ 4$ |
| $9$ | $8$ | $d$ 为质数 |
| $10$ | $23$ | 无 |