ll pow(ll x,ll n) {

    ll res = ;

    x%=mod;

    while (n) {

        if(n&) res = res*x%mod;

        x = x*x %mod;

        n >>=;

    }

    return res;

}

ll C(ll n,ll m) {

    if(n < m) return ;

    // c(n,m) = n!/m!/(n-m)!

    ll res = ;

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

        ll a = (n+i-m)%mod;

        ll b = i%mod;

        res = res*(a*pow(b,mod-)%mod)%mod;

    }

    return res;

}

ll Lucas(ll n,ll m) {

    if(m == ) return ;

    return C(n%mod, m%mod) * Lucas(n/mod,m/mod)%mod;

}