Define $f(j) \equiv \sum_{i=0}^{n-1} C_{i\cdot d}^{j} \pmod M$, where $0 \leq f(j) < M$, and $n, d, M$ are given values.

Given $m$, output the value of $f(0) \oplus f(1) \oplus f(2) \oplus \cdots \oplus f(m - 1)$.

Here, $C_{n}^{m}$ is the binomial coefficient "n choose m", defined as $C_{n}^{m} = \displaystyle \begin{cases}\frac{n!}{m!\cdot (n-m)!}&, 0\leq m\leq n \cr 0&, \text{otherwise}\end{cases}$. $\oplus$ denotes the bitwise XOR operation.

Input

A single line containing four integers $n, m, d, M$, separated by spaces.

Output

A single line containing the answer.

Examples

Input 1

3 2 3 998244353

Output 1

10

Note 1

$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) \oplus f(1) = 3 \oplus 9 = 10$

Subtasks

This problem uses bundled testing.

For all test cases, $1 \leq d \leq 100$, $1 \leq m\cdot d \leq 3\times 10^6$, $1 \leq n\cdot d \leq 10^9$, and $10^8 \leq M \leq 10^9$.