$O(p+\log_pn)$ 计算 ${n\choose m}\bmod p$ 的算法，$p$ 为素数。
$${p\choose i}=\frac pi{p-1\choose i-1}$$
于是对 $1\le i\le p-1$，有 ${p\choose i}\equiv 0\pmod p$。
$$(1+x)^p\equiv {p\choose 0}+{p\choose 1}x+\cdots +{p\choose p}x^p\equiv 1+x^p\pmod p$$
对 ${n\choose m}$，不妨设 $n=k_1p+r_1,m=k_2p+r_2$，于是有
$$(1+x)^n\equiv (1+x)^{k_1p+r_1}\equiv ((1+x)^p)^{k_1}(1+x)^{r_1}\equiv (1+x^p)^{k_1}(1+x)^{r_1}\pmod p$$
对比左右两边 $x_m$ 的系数，有
$${n\choose m}\equiv {k_1\choose k_2}{r_1\choose r_2}\pmod p$$
于是递归处理，有
$$\text{Lucas}(n,m)\equiv \text{Lucas}(\lfloor \frac np\rfloor,\lfloor \frac mp\rfloor){n\bmod p\choose m\bmod p}$$
$O\left(\sum p_i^k+\sum \log_2 n\log_{p_i^k}n\right)$ 计算 ${n\choose m}\bmod p$ 的算法，其中 $p=\prod p_i^k$。
考虑计算 ${n\choose m}\equiv x_i\pmod {p_i^k}$，然后中国剩余定理合并答案。
$$ {n\choose m}\equiv \frac {n!}{m!(n-m)!}\pmod {p^k} $$
分子不一定与模数互质，不能直接使用逆元计算。考虑提取出 $n!$ 所有的 $p$ 因子，记为 $g(n)$，同时记 $f(n)=\frac {n!}{p^{g(n)}}$。代入上式，有
$$ \cfrac{\frac {n!}{p^{g(n)}}}{\frac {m!}{p^{g(m)}}\frac {(n-m)!}{p^{g(n-m)}}}p^{g(n)-g(m)-g(n-m)}\equiv \cfrac{f(n)}{f(m)f(n-m)}p^{g(n)-g(m)-g(n-m)}\pmod {p^k} $$
于是有 $(f(n),p^k)=1$，可以参与逆元计算。设 $n=ap^k+b$。
$$ n!=\prod_{i=1,p\mid i}^ni \prod_{i=1,p\not\mid i}^ni=(\lfloor\frac np\rfloor)!p^{\lfloor\frac np\rfloor}(\prod_{i=1,p\not\mid i}^{p^k}i)^a\prod_{i=1,p\not\mid i}^b i $$
于是有
$$ f(n)=f(\lfloor\frac np\rfloor)(\prod_{i=1,p\not\mid i}^{p^k}i)^a\prod_{i=1,p\not\mid i}^b i $$ $$ g(n)=g(\lfloor\frac np\rfloor)+\lfloor\frac np\rfloor $$
经过 $O\left(\sum p_i^k\right)$ 预处理后即可 $O\left(\sum \log_2 n\log_{p^k}n\right)$ 递归计算答案。