一道类似的题目：uoj 86 mx的组合数。

基本原理是，注意到我们有 Lucas 定理，我们可以把组合数拆进制，转化成数位 dp 问题。

问题转化为进行 $O(\log_pv)$ 轮两个长为 $p$ 的数组的下标乘法卷积和逐点加法。

逐点加法容易做到 $O(p)$，关键问题在于乘法卷积。

注意到 $p$ 是质数，因此我们直接找出原根，然后把除了 $0$ 位置之外的数全部用离散对数投影到 $[0,p-1)$ 上，转化成普通卷积，NTT 即可维护。

忽略掉找原根部分的复杂度，总复杂度 $O(p\log n)$，足以通过此题。