题目描述

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

输出格式

一行一个整数表示答案。

3 2 3 998244353

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$。