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

$$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 = 0Cnm=0。）

小葱在 NOIP 的时候学习了 Cij\mathrm{C}_i^jCij 和 $k$ 的倍数关系，现在他想更进一步，研究更多关于组合数的性质。小葱发现，Cij\mathrm{C}_i^jCij 是否是 $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$$

的值。