Lucas

定理是用来求 ，为素数的值。（注意：一定是素数）
定理用来解决大组合数求模是很有用的。
由决定

ll fac[10];
ll p=3;
void init(){
    fac[0]=1;
    for(ll i=1;i<p;i++)
        fac[i]=fac[i-1]*i%p; 
}
ll power(ll a,ll b,ll mod){
    ll ans=1;
    while(b){
        if(b&1) ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ans;
}
ll C(ll n,ll m){
    if(n<m)
        return 0;
    return fac[n]*power(fac[m]*fac[n-m],p-2,p)%p;
}
ll lucas(ll n,ll m){
    if(m==0)
        return 1;
    return (C(n%p,m%p)*lucas(n/p,m/p))%p;
}