typedef long long ll;

/**********************************

 大组合数取模之lucas定理模板,1<=n<=m<=1e9,1<p<=1e6，p必须为素数

 输入：C(n,m)%p 调用lucas(n,m,p)

 复杂度：min(m,p)*log(m)

 ***********************************/

//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==){d=a;x=;y=;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=,rey=;

    ll td=;

    extendgcd(A,M,td,rex,rey);

    return (rex%M+M)%M;

}

ll C(ll n,ll m,ll p)

{

    if(m>n) return ;

    ll up=,dn=;

    for(int i=;i<m;i++)

    {

        up = up*(n-i)%p;

        dn = dn*(i+)%p;

    }

    return up*GetNi(dn, p)%p;

}

ll lucas(ll n,ll m,ll p)

{

    if(m==) return ;

    return C(n%p,m%p,p)*lucas(n/p,m/p,p) % p;

}