题目描述

定义

$$f(j) \equiv \sum_{i=0}^{n-1} C_{i \cdot d}^{j} \pmod{M},\quad 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 \\ 0 &, \text{otherwise} \end{cases} $$

$\mathrm{xor}$ 表示异或和。

输入格式

一行四个整数 $n$, $m$, $d$, $M$，由空格隔开。

输出格式

一行一个整数表示答案。

样例

输入：
3 2 3 998244353

输出：
10

解释：

$$\begin{aligned} 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 \end{aligned} $$

数据范围与提示

本题采用捆绑测试。

对于所有测试包均满足：

• $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		$m \leq 8000$
5	7	$d = 1$
6	22	$\gcd(d, M) = 1$
7	7	$d = 2$
8		$d = 4$
9	8	$d$ 为质数
10	23	无