1304: 「SHOI2017」组合数问题
[Creator : ]
Description
组合数 $C_n^m$ 表示的是从 $n$ 个互不相同的物品中选出 $m$ 个物品的方案数。举个例子， 从 $(1, 2, 3)$ 三个物品中选择两个物品可以有 $(1, 2)$，$(1, 3)$，$(2, 3)$ 这三种选择方法。根据组合数的定义，我们可以给出计算组合数 $C_n^m$ 的一般公式：
$ C_n^m = \frac {n!} {m! \ (n - m)!} $
其中 $n! = 1 \times 2 \times \cdots \times n$。（特别地，当 $n = 0$ 时，$n! = 1$；当 $m > n$ 时，$C_n^m = 0$。）
小葱在 NOIP 的时候学习了 $C_i^j$ 和 $k$ 的倍数关系，现在他想更进一步，研究更多关于组合数的性质。小葱发现，$C_i^j$ 是否是 $k$ 的倍数，取决于 $C_i^j \bmod k$ 是否等于 $0$，这个神奇的性质引发了小葱对 $\mathrm{mod}$ 运算（取余数运算）的兴趣。现在小葱选择了是四个整数 $n, p, k, r$，他希望知道
$\left( \sum_{i = 0}^\infty C_{nk}^{ik + r} \right) \bmod p,$
即
$\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$
的值。
$ C_n^m = \frac {n!} {m! \ (n - m)!} $
其中 $n! = 1 \times 2 \times \cdots \times n$。（特别地，当 $n = 0$ 时，$n! = 1$；当 $m > n$ 时，$C_n^m = 0$。）
小葱在 NOIP 的时候学习了 $C_i^j$ 和 $k$ 的倍数关系，现在他想更进一步，研究更多关于组合数的性质。小葱发现，$C_i^j$ 是否是 $k$ 的倍数，取决于 $C_i^j \bmod k$ 是否等于 $0$，这个神奇的性质引发了小葱对 $\mathrm{mod}$ 运算（取余数运算）的兴趣。现在小葱选择了是四个整数 $n, p, k, r$，他希望知道
$\left( \sum_{i = 0}^\infty C_{nk}^{ik + r} \right) \bmod p,$
即
$\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
第一行有四个整数 $n, p, k, r$，所有整数含义见问题描述。
Output
一行一个整数代表答案。
Constraints
对于 $30\%$ 的测试点，$1 \leq n, k \leq 30$，$p$ 是质数；
对于另外 $5\%$ 的测试点，$p = 2$；
对于另外 $5\%$ 的测试点，$k = 1$；
对于另外 $10\%$ 的测试点，$k = 2$；
对于另外 $15\%$ 的测试点，$1 \leq n \leq 10^3, 1 \leq k \leq 50$，$p$ 是质数；
对于另外 $15\%$ 的测试点，$1 \leq n \times k \leq 10^6$，$p$ 是质数；
对于另外 $10\%$ 的测试点，$1 \leq n \leq 10^9, 1 \leq k \leq 50$，$p$ 是质数；
对于 $100\%$ 的测试点，$1 \leq n \leq 10^9, 0 \leq r < k \leq 50, 2 \leq p \leq 2^{30} - 1$。
对于另外 $5\%$ 的测试点，$p = 2$；
对于另外 $5\%$ 的测试点，$k = 1$；
对于另外 $10\%$ 的测试点，$k = 2$；
对于另外 $15\%$ 的测试点，$1 \leq n \leq 10^3, 1 \leq k \leq 50$，$p$ 是质数；
对于另外 $15\%$ 的测试点，$1 \leq n \times k \leq 10^6$，$p$ 是质数；
对于另外 $10\%$ 的测试点，$1 \leq n \leq 10^9, 1 \leq k \leq 50$，$p$ 是质数；
对于 $100\%$ 的测试点，$1 \leq n \leq 10^9, 0 \leq r < k \leq 50, 2 \leq p \leq 2^{30} - 1$。
Sample 1 Input
2 10007 2 0
Sample 1 Output
8
$\mathrm{C}_4^0 + \mathrm{C}_4^2 + \mathrm{C}_4^4 + \cdots = 1 + 6 + 1 = 8$
Sample 2 Input
20 10007 20 0
Sample 2 Output
176