题目描述

定义 $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}\ =\ \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$，由空格隔开。

输出格式

一行一个整数表示答案。

样例

input

3 2 3 998244353

output

10

$f(0)\ \equiv\ C_0^0\ +\ C_3^0\ +\ C_6^0\ \equiv\ 1\ +\ 1\ +\ 1\ \equiv\ 3\ (\bmod\ 998244353)$

$f(1)\ \equiv\ C_0^1\ +\ C_3^1\ +\ C_6^1\ \equiv\ 0\ +\ 3\ +\ 6\ \equiv\ 9\ (\bmod\ 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$。