Description

The binomial coefficient $C_n^m$ denotes the number of ways to choose $m$ items from $n$ distinct items. For example, choosing two items from $(1, 2, 3)$ has three possibilities: $(1, 2)$, $(1, 3)$, $(2, 3)$. By definition, a general formula to compute $C_n^m$ is:

$$C_n^m = \frac {n!} {m! \ (n - m)!}$$

where $n! = 1 \times 2 \times \cdots \times n$. (In particular, when $n = 0$, $n! = 1$; when $m > n$, $C_n^m = 0$.)

Xiaocong learned about the divisibility relationship between $C_i^j$ and $k$ during NOIP, and now he wants to go further and study more properties of binomial coefficients. He noticed that whether $C_i^j$ is a multiple of $k$ depends on whether $C_i^j \bmod k$ equals $0$. This intriguing fact sparked his interest in the $\mathrm{mod}$ operation (the remainder operation). Now Xiaocong chose four integers $n, p, k, r$, and he wants to know

$$\left( \sum_{i = 0}^\infty C_{nk}^{ik + r} \right) \bmod p,$$

that is,

$$\left( C_{nk}^{r} + C_{nk}^{k + r} + C_{nk}^{2k + r} + \cdots + C_{nk}^{(n - 1)k + r} + C_{nk}^{nk + r} + \cdots \right) \bmod p.$$

Input Format

The first line contains four integers $n, p, k, r$. All symbols have the meanings given in the problem statement.

Output Format

Output a single integer, the answer.

2 10007 2 0

8

20 10007 20 0

176

Hint

For $30\%$ of the test points, $1 \leq n, k \leq 30$, and $p$ is prime.
For another $5\%$ of the test points, $p = 2$.
For another $5\%$ of the test points, $k = 1$.
For another $10\%$ of the test points, $k = 2$.
For another $15\%$ of the test points, $1 \leq n \leq 10^3$, $1 \leq k \leq 50$, and $p$ is prime.
For another $15\%$ of the test points, $1 \leq n \times k \leq 10^6$, and $p$ is prime.
For another $10\%$ of the test points, $1 \leq n \leq 10^9$, $1 \leq k \leq 50$, and $p$ is prime.
For $100\%$ of the test points, $1 \leq n \leq 10^9$, $0 \leq r < k \leq 50$, $2 \leq p \leq 2^{30} - 1$.

Translated by ChatGPT 5