组合数 表示的是从 个互不相同的物品中选出 个物品的方案数。举个例子， 从 三个物品中选择两个物品可以有 ，， 这三种选择方法。根据组合数的定义，我们可以给出计算组合数 的一般公式：

Cmn=n!m! (n−m)!

其中 。（特别地，当 时，；当 时，。）

小葱在 NOIP 的时候学习了 和 的倍数关系，现在他想更进一步，研究更多关于组合数的性质。小葱发现， 是否是 的倍数，取决于 Cjimodk 是否等于 ，这个神奇的性质引发了小葱对 运算（取余数运算）的兴趣。现在小葱选择了是四个整数 ，他希望知道

(∞∑i=0Cik+rnk)modp,

即

(Crnk+Ck+rnk+C2k+rnk+⋯+C(n−1)k+rnk+Cnk+rnk+⋯)modp

的值。