ll PowMod(ll a,ll b,ll MOD){
ll ret=;
while(b){
if(b&) ret=(ret*a)%MOD;
a=(a*a)%MOD;
b>>=;
}
return ret;
}
ll fac[];
ll Get_Fact(ll p)
{
fac[]=;
for(int i=;i<=p;i++)
fac[i]=(fac[i-]*i)%p;
}
ll Lucas(ll n,ll m,ll p){
ll ret=;
while(n&&m){
ll a=n%p,b=m%p;
if(a<b) return ;
ret=(ret*fac[a]*PowMod(fac[b]*fac[a-b]%p,p-,p))%p;
n/=p;
m/=p;
}
return ret;
}