模数比较大底数比较小的组合数算法

求 $\binom n k\bmod m$, $n, k\leq 10^6, m\leq 10^9$。

首先 exLucas 应该是可以的？但是考场容易忘掉。所以来个简单方法。

令 $\prod p_i^{d_i} = m$，则 $x!$ 可以表示为 $q_x\prod p_i^{e_{x, i}}$，这里 $\gcd(q_x, m) = 1$。因此，

$q_x, \frac 1{q_x}, e_{x, i}, {p_i}^x$ 都是容易在 $O(n\log m)$ 时间内预处理出来的。则询问容易在 $O(\log m)$ 时间算出。