2452: #2143. 「SHOI2017」组合数问题

组合数 Cnm\mathrm{C}_n^mC​n​m​​ 表示的是从 $n$ 个互不相同的物品中选出 $m$ 个物品的方案数。举个例子， 从 $(1,2,3)$ 三个物品中选择两个物品可以有 $(1,2)$，$(1,3)$，$(2,3)$ 这三种选择方法。根据组合数的定义，我们可以给出计算组合数 Cnm\mathrm{C}_n^mC​n​m​​ 的一般公式：

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

其中 $n!=1\times 2\times \cdots \times n$。（特别地，当 $n=0$ 时，$n!=1$；当 $m>n$ 时，Cnm=0\mathrm{C}_n^m = 0C​n​m​​=0。）

小葱在 NOIP 的时候学习了 Cij\mathrm{C}_i^jC​i​j​​ 和 $k$ 的倍数关系，现在他想更进一步，研究更多关于组合数的性质。小葱发现，Cij\mathrm{C}_i^jC​i​j​​ 是否是 $k$ 的倍数，取决于 $C_i^{j}modk$ 是否等于 $0$，这个神奇的性质引发了小葱对 $\mathrm{m}\mathrm{o}\mathrm{d}$ 运算（取余数运算）的兴趣。现在小葱选择了是四个整数 $n,p,k,r$，他希望知道

$$\left(\sum _{i=0}^{\infty }{C}_{nk}^{ik+r}\right)modp,$$

即

$$\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)modp$$

的值。

输入格式

第一行有四个整数 $n,p,k,r$，所有整数含义见问题描述。

输出格式

一行一个整数代表答案。

样例

样例输入 1

2 10007 2 0

样例输出 1

8

样例解释 1

C40+C42+C44+⋯=1+6+1=8\mathrm{C}_4^0 + \mathrm{C}_4^2 + \mathrm{C}_4^4 + \cdots = 1 + 6 + 1 = 8C​4​0​​+C​4​2​​+C​4​4​​+⋯=1+6+1=8。

样例输入 2

20 10007 20 0

样例输出 2

176

数据范围与提示

对于 $30\%$ 的测试点，$1\le n,k\le 30$，$p$ 是质数；
对于另外 $5\%$ 的测试点，$p=2$；
对于另外 $5\%$ 的测试点，$k=1$；
对于另外 $10\%$ 的测试点，$k=2$；
对于另外 $15\%$ 的测试点，1≤n≤103,1≤k≤501 \leq n \leq 10^3, 1 \leq k \leq 501≤n≤10​3​​,1≤k≤50，$p$ 是质数；
对于另外 $15\%$ 的测试点，1≤n×k≤1061 \leq n \times k \leq 10^61≤n×k≤10​6​​，$p$ 是质数；
对于另外 $10\%$ 的测试点，1≤n≤109,1≤k≤501 \leq n \leq 10^9, 1 \leq k \leq 501≤n≤10​9​​,1≤k≤50，$p$ 是质数；
对于 $100\%$ 的测试点，1≤n≤109,0≤r<k≤50,2≤p≤230−11 \leq n \leq 10^9, 0 \leq r < k \leq 50, 2 \leq p \leq 2^{30} - 11≤n≤10​9​​,0≤r<k≤50,2≤p≤2​30​​−1。