Lucas定理

求解大组合数对素数（不大于100000）取模的结果。。题目还没做出来，先把模板记着了。

ll fac[maxn], inv[maxn];  
  
ll pow_mod(ll a, int n, int mod) {  
    ll ret = 1;  
    while (n) {  
        if (n&1) ret = ret * a % mod;  
        a = a * a % mod;  
        n >>= 1;  
    }  
    return ret;  
}  
  
void init(int n) {  
    fac[0] = 1;  
    for (int i = 1; i < n; i++) fac[i] = fac[i-1] * i % n;  
    inv[n-1] = pow_mod(fac[n-1], n-2, n);  
    for (int i = n - 2; i >= 0; i--) inv[i] = inv[i+1] * (i+1) % n;  
}  
  
ll C (int n, int m, int mod) {  
    if (m > n || m < 0 || n < 0) return    0;  
    return fac[n] * inv[m] % mod * inv[n-m] % mod;  
}  
  
ll lucas(ll n, ll m, int mod) {  
    if (m == 0) return 1;  
    return lucas(n / mod, m / mod, mod) * C(n % mod, m % mod, mod) % mod;  
}