typedef long long ll;
//ax + by = gcd(a,b)
//传入固定值a,b.放回 d=gcd(a,b), x , y
void extendgcd(ll a,ll b,ll &d,ll &x,ll &y)
{
if(b==0){d=a;x=1;y=0;return;}
extendgcd(b,a%b,d,y,x);
y-=x*(a/b);
}
//Ax=1(mod M)，gcd(A,M)==1
//输入：10^18>=A,M>=1
//输出：返回x的范围是[1,M-1]
ll GetNi(ll A,ll M)
{
ll rex=0,rey=0;
ll td=0;
extendgcd(A,M,td,rex,rey);
return (rex%M+M)%M;
}
ll C(ll n,ll m,ll p)
{
if(m>n) return 0;
ll up=1,dn=1;
for(int i=0;i<m;i++)
{
up = up*(n-i)%p;
dn = dn*(i+1)%p;
}
return up*GetNi(dn, p)%p;
}
ll lucas(ll n,ll m,ll p)
{
if(m==0) return 1;
return C(n%p,m%p,p)*lucas(n/p,m/p,p) % p;
}