static inline ll powmod(unsigned a, unsigned b){
  register ll x=1,y=a;
  while(b){
    if(b&1){
      x*=y; if(x>=MOD)x%=MOD;
    }
    y*=y; if(y>=MOD)y%=MOD;
    b>>=1;
  }
  return x;
}

static inline ll InverseMod(ll n){
  return powmod(n,MOD-2);
}

static inline ll prodMod(ll minx,ll maxx){
    for(unsigned i=minx+1; i<=maxx; i++){
      minx*=i; if(minx>=MOD)minx%=MOD;
    }
  return minx;
}

static inline ll factMOD(unsigned n){
  register ll ans0=1,ans1=1;register unsigned i,m;
  for(i=1,m=(n+1)>>1; i<m; i++){
    ans0*=(i<<1); if(ans0>=MOD)ans0%=MOD;
    ans1*=((i<<1)+1); if(ans1>=MOD)ans1%=MOD;
  }
  return ans0*ans1%MOD;
}

static inline ll chemin(ll x, ll y){
  return (prodMod(x+1,x+y) *
      InverseMod(factMOD(y)))%MOD;
}