【数论】Lucas

就是个Lucas

对于质数p，有C(n,m)=C(n/p,m/p)*C(n%p,m%p)%p

代码

ll C(ll a,ll b)

{

    if(a<b)  return ;

    if(!b)  return ;

    if(a<p&&b<p)  return fac[a]*inv[b]%p*inv[a-b]%p;

    return C(a%p,b%p)*C(a/p,b/p)%p;

}