组合数 Cnm\mathrm{C}_n^mCnm 表示的是从 nnn 个互不相同的物品中选出 mmm 个物品的方案数。举个例子， 从 (1,2,3)(1, 2, 3)(1,2,3) 三个物品中选择两个物品可以有 (1,2)(1, 2)(1,2)，(1,3)(1, 3)(1,3)，(2,3)(2, 3)(2,3) 这三种选择方法。根据组合数的定义，我们可以给出计算组合数 Cnm\mathrm{C}_n^mCnm 的一般公式：
Cmn=n!m! (n−m)!
其中 n!=1×2×⋯×nn! = 1 \times 2 \times \cdots \times nn!=1×2×⋯×n。（特别地，当 n=0n = 0n=0 时，n!=1n! = 1n!=1；当 m>nm > nm>n 时，Cnm=0\mathrm{C}_n^m = 0Cnm=0。）
小葱在 NOIP 的时候学习了 Cij\mathrm{C}_i^jCij 和 kkk 的倍数关系，现在他想更进一步，研究更多关于组合数的性质。小葱发现，Cij\mathrm{C}_i^jCij 是否是 kkk 的倍数，取决于 Cjimodk 是否等于 000，这个神奇的性质引发了小葱对 mod\mathrm{mod}mod 运算（取余数运算）的兴趣。现在小葱选择了是四个整数 n,p,k,rn, p, k, rn,p,k,r，他希望知道
(∞∑i=0Cik+rnk)modp,
即
(Crnk+Ck+rnk+C2k+rnk+⋯+C(n−1)k+rnk+Cnk+rnk+⋯)modp
的值。