即求

$$\sum_{0\le i\le n}\sum_{0\le j\le\min\{m,i\}}[k|\binom ij] $$

不妨 $m\leftarrow\min\{m,n\}$ 使得 $m\le n$，那么答案即为

$$\frac{m(m+1)}{2}+\sum_{0\le i\le n}\sum_{0\le j\le m}[\binom ij\bmod k=0] $$

由于 $k$ 为质数，我们首先掏出一个 Lucas 定理，问题变成数位 dp，随便做一下就好了。

单轮复杂度大概是 $O(k^2\log_kv)$ 的？

参考代码。