P3746 [Six-Province Joint Exam 2017] Binomial Coefficients Problem

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

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

Output a single integer, the answer.

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