题解
注意到是组合数对一个质数 \(k\) 取余的问题，想到卢卡斯定理，即 \(C_{x}^y = C_{x\mod k}^{y\mod k} \times C_{x/ k}^{y/k} \mod k\)。
发现如果将 \(x,y\) 进行 \(k\) 进制拆分：
\(x = a_0 + a_1 \times k + a_2\times k^2\dots a_i\times k^i,y = b_0 + b_1 \times k + b_2\times k^2\dots b_i\times k^i\)
那么最后结果就是 \(C_{a_0}^{b_0}\times C_{a_1}^{b_1}\dots \times C_{a_i}^{b_i}\mod k\)。
因为 \(a_i,b_i\) 都是属于 \([0,k-1]\) 的，所以对于其中的任意一个组合式，都不可能含有因子 \(k\)，因此上式答案等于 \(0\) 的充要条件就是 \(\exist C_{a_i}^{b_i} = 0\)，即 \(b_i > a_i\)。存在不好求，正难则反，用总方案数减去 \(\forall a_i\ge b_i\) 的方案数，这样还顺便满足了题目中 \(j\le i\) 的限制。