模板—卢卡斯定理+乘法逆元

 1 LL inv(LL a,LL b)
 2 {
 3     LL ans=1,res=a;
 4     while(b)
 5     {
 6         if(b&1)ans=ans*res%p;
 7         res=res*res%p;
 8         b=b>>1;
 9     }
10     return ans%p;
11 }
12 LL C(LL n,LL m)
13 {
14     if(n<m)return 0;
15     return jc[n] * inv(jc[m],p-2)%p * inv(jc[n-m],p-2)%p;
16 }
17 LL Lucas(LL n,LL m)
18 {
19     if(!m)return 1;
20     return C(n%p,m%p)*Lucas(n/p,m/p)%p;
21 }