const int _MOD_ = (int)1e9 + 9;

inline bool Eq( ll a, ll b, int mod = _MOD_ ) { return (a - b) % mod == 0; }
inline int Add( int a, int b, int mod = _MOD_ ) { a += b; return a >= mod ? a - mod : a; }
inline int Sub( int a, int b, int mod = _MOD_ ) { a -= b; return a < 0 ? a + mod : a; }
inline int Mul( int x, int y, int mod = _MOD_ ) { return ((ll)x * y) % mod; }
inline int Sqr( int a, int mod = _MOD_ ) { return Mul(a, a, mod); }

int Pow( int x, ll n, int mod = _MOD_ )
{
  int r = mod > 1 ? 1 : 0;
  for (; n; n /= 2)
  {
    if (n & 1)
      r = Mul(r, x, mod);
    x = Mul(x, x, mod);
  }
  return r;
}

int Euclid( int a, int b, int &x1, int &y1 ) // a * x + b * y = gcd
{
  int d1 = a; x1 = 1, y1 = 0;
  int d2 = b, x2 = 0, y2 = 1; 
  while (d2 != 0) 
  {
    int k = d1 / d2;
    int x3 = x1 - x2 * k, y3 = y1 - y2 * k, d3 = d1 - d2 * k;
    x1 = x2, y1 = y2, d1 = d2;
    x2 = x3, y2 = y3, d2 = d3;
    Assert(abs(x3) <= b && abs(y3) <= a);
  }
  Assert(a * x1 + b * y1 == d1);
  return d1; // gcd
}

int Inv( int a, int m = _MOD_ ) // x * a + y * m == 1
{
  int x, y, gcd = Euclid(m, a, y, x);
  Assert(gcd == 1);
  Assert(Eq((ll)x * a, 1, m));
  return x < 0 ? x + m : x;
}

int Div( int a, int b, int p = _MOD_ )
{
  return Mul(a, Inv(b, p), p);
}

// x = a1(mod m1), x = a2(mod m2), (m1, m2) = 1
int KTO( int a1, int m1, int a2, int m2 ) // m1 * m2 should fit into 31-bit integer type
{
  return ((ll)a1 * m2 * Inv(m2 % m1, m1) + (ll)a2 * m1 * Inv(m1 % m2, m2)) % (m1 * m2);
}

const int maxFact = (int)1e5 + 10;
int f[maxFact];

void CalcFactorials( int mod = _MOD_ )
{
  int n = sizeof(f) / sizeof(f[0]);
  f[0] = 1;
  for (int i = 0; i < n - 1; i++)
    f[i + 1] = Mul(f[i], i + 1, mod);
}

int C( int n, int k ) { return Div(f[n], Mul(f[k], f[n - k])); }