const int mod = ;

 long long quickpow(long long a, long long b) {

     if (b < ) return ;

     long long ret = ;

     a %= mod;

     while(b) {

         if (b & ) ret = (ret * a) % mod;

         b >>= ;

         a = (a * a) % mod;

     }

     return ret;

 }

 long long inv(long long a) {

     return quickpow(a, mod - );

 }  

 ll extend_gcd(ll a, ll b, ll &x, ll &y) {

     if (b == ) {

         x = , y = ;

         return a;

     }

     else {

         ll r = extend_gcd(b, a % b, y, x);

         y -= x * (a / b);

         return r;

     }

 }

 ll inv(ll a, ll n) {

     ll x, y;

     extend_gcd(a, n, x, y);

     x = (x % n + n) % n;

     return x;

 }  

 const int mod = ;

 const int maxn = ;

 int inv[maxn];

 inv[] = ;

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

     inv[i] = inv[mod % i] * (mod - mod / i) % mod;  

 fac[]=fac[]=;

 for(int i=;i<=MAXN;i++)fac[i]=fac[i-]*i%mod;

 inv[MAXN]=quipow(fac[MAXN],mod-);

 for(int i=MAXN-;i>=;i--)inv[i]=inv[i+]*(i+)%mod;