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

定理 Cmn%p =Cm/pn/p∗Cm%pn%p

证明：

预备知识①  Cip%p=0p 为素数且，i≠p and i≠0

预备知识②   二项式定理:  

特殊情况 当a=1,b=x

(1+x)n=∑i=0nCinxi

证明如下

n = sp + q;

m = tp + r;

（1+x)n=(1+x)sp+q≡(1+x)sp∗(1+x)q≡(1+xp)s∗(1+x)q−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−(①)

≡∑i=0sCis∗xp∗i∗∑j=0qCjqxj(②)

{直接展开即可获得}

又知(1+x)n=∑i=0nCin∗xi

求等式两边 xtp+r的系数

left=Cmn

right=Cts∗Crq(只有当i = t，j = r的时候才有xtp+r的系数

于是问题得证

代码参考

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;}