若 \(p\) 为质数，则对于任意整数 \(1\le m \le n\)，有：
\(C_n^m \equiv C_{n \div p}^{m \div p} \times C_{n\mod p}^{m\mod p} (mod~p)\)
也就是把 \(n\) 和 \(m\) 表示成 \(p\) 进制数，并且对 \(p\) 进制数下的每一位分别计算组合数，累乘起来。
CODE
inline int power(int x,int y,int p){
int res=1;
while(y){
if(y&1) res=res*x%p;
x=x*x%p;
y>>=1;
}
return res%p;
}
inline int C(int x,int y,int p){
if(y>x) return 0;
return jc[x]*power(jc[y]*jc[x-y]%p,p-2,p)%p;//乘上逆元
}
inline int Lucas(int x,int y,int p){
if(!y) return 1;
return C(x%p,y%p,p)*Lucas(x/p,y/p,p)%p;
}