跟下面那道题比起来属于是纯纯的小清新题了，这就是原友出题人和原批出题人的差距。不过当时的 FFT 应该没有现在这么普及，就像原神在最初几年也没有引起轩然大波一样。

这种组合数取模肯定考虑卢卡斯定理，况且 $n \lt p^{10}$ 也算是提醒你了。

将 $n$ 和 $k$ 写成 $p$ 进制数 $\overline{n_N...n_0}$ 和 $\overline{k_N...k_0}$，根据卢卡斯定理有 $C_n^k=\prod_i{C_{n_i}^{k_i}}$。显然每个 $k_i$ 的贡献是可以分开算的。

令 $f_{i,j}$ 表示前 $i$ 位组合数累乘后 $\%p=j$ 的方案数，$g_{i,j}$ 表示使得 $C_{n_i}^k \%p = j$ 的 $k$ 的数量，转移是简单的：

$$f_{i,j}=\sum_{(x\times y) \%p=j}{f_{i-1,x} g_{i,y}}$$

这转移式和卷积的相似度可以与原神媲美了，然而这个下标是相乘而不是相加。

但这玩意属于是典中典了，直接把下标对 $p$ 的原根取对数就可以转化成相加了，具体见 “[SDOI2015]序列统计”。

重新定义一下，令当前选择的原根是 $G$。

令 $f_{i,j}$ 表示前 $i$ 位组合数累乘后 $\%p=G^j$ 的方案数，$g_{i,j}$ 表示使得 $C_{n_i}^k \%p = G^j$ 的 $k$ 的数量，将转移写成和卷积：

$$F_i=\sum_{j\ge 0}{f_{i,j}x^j}\quad\quad G_i=\sum_{j\ge 0}{g_{i,j}x^j}$$

$$\Rightarrow F_{i}=\sum_{j\ge 0}(\sum_{(x+y)\%(p-1)=j}{f_{i-1,x} g_{i,y}})x^j=F_{i-1}G_i$$

大概就是这样，注意下标相加实际是指数相加，所以根据费马小定理对 $p-1$ 取模。以及这样卷积出来会有下标大于 $p-1$ 的项，及时合并到前面即可。

介于答案模数较小，使用 FFT 计算卷积，时间复杂度大概是 $O(10p\log(p))$。

勉强加入“超级无敌神仙炫酷无敌原神大王”豪华套餐。