lucas 定理，组合数取模

Lucas 定理求 <nobr> Cmn%p </nobr> 的值，如果n，m的值过大，不易直接求出，所以利用lucas定理

定理 <nobr> Cmn%p </nobr> <nobr> =Cm/pn/p∗ </nobr> <nobr> Cm%pn%p </nobr>
证明：百度百科

预备知识①   <nobr> Cip%p=0 </nobr>p 为素数且， <nobr> i≠p and i≠0 </nobr>
预备知识②   二项式定理:  
特殊情况 当 <nobr> a=1,b=x </nobr>
<nobr> (1+x)n=∑i=0nCinxi </nobr>
证明如下
n = sp + q;
m = tp + r;
<nobr> （1+x)n=(1+x)sp+q≡(1+x)sp∗(1+x)q≡(1+xp)s∗(1+x)q−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− </nobr>(①)
<nobr> ≡∑i=0sCis∗xp∗i∗∑j=0qCjqxj </nobr>(②)
{直接展开即可获得}

又知 <nobr> (1+x)n=∑i=0nCin∗xi </nobr>
求等式两边 <nobr> xtp+r </nobr>的系数
<nobr> left=Cmn </nobr>
<nobr> right=Cts∗Crq </nobr>(只有当i = t，j = r的时候才有 <nobr> xtp+r </nobr>的系数
于是问题得证
代码参考

long long qpow(long long a,long long b,long long m)
{
 long long ans = 1;
 a %= m;
 while(b>0)
 {
     if(b&1)
     ans = ans*a%m;
     a = a*a%m;
     b >>= 1;
 }
    return ans;
}
long long  C(long long  n,long long m,long long p)
{
    if(m>n)
        return 0;
    long long tmp1 = 1,tmp2 = 1;
    for(long long i = n-m+1;i <= n; ++i)
       {
            tmp1 = tmp1*i % p;
            tmp2 = tmp2 *(n-i+1) %p;
       }
    return  tmp1*qpow(tmp2,p-2,p)%p;
}
int lucas(int n,int m,int p)
{
    if(m==0)
        return 1;
    return lucas(n/p,m/p,p)*C(n%p,m%p,p)%p;
}