组合计数·卢卡斯定理

对于大组合数对某素数$p$的模，可以使用Lucas定理，程序代码如下：

ll C(ll n, ll m, ll p){
    if(m > n) return 0;
    return fac[n] * power(fac[m] * fac[n - m], p - 2) % p;
}

ll Lucas(ll n, ll m, ll p){
    if(!m) return 1ll;
    return C(n % p, m % p, p) * Lucas(n / p, m / p, p) % p;
}

其中fac[n]表示$n!mod p$。

理论知识：

对于非负整数$m$和$n$，以及素数$p$，则有下式成立：

$inom{m}{n} equiv prod_{i=0}^{k}{inom{m_i}{n_i}}$，其中：

$m=m_kp^k+m_{k-1}p^{k-1}+cdots+m_1p+m_0$且$n=n_kp^k+n_{k-1}p^{k-1}+cdots+n_1p+n_0$。