#include "bits/stdc++.h"

#define all(x)   x.begin(), x.end()
#define NL       std::cout << '\n'

using lnt = long long;

const int inf = 0x3f3f3f3f;
const lnt linf = 1ll << 62;

int main() {
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  const int mo = 1e9 + 9;
  auto inv = [&](lnt x) {
    int e = mo - 2;
    lnt ret = 1;
    while (e) {
      if (e & 1) { ret = ret * x % mo; }
      e >>= 1; x = x * x % mo;
    }
    return ret;
  };
  int m, Q; std::cin >> m >> Q;
  lnt contri = 0;
  lnt dep = 1;
  lnt k = 1;
  while (Q--) {
    contri = (contri + dep * m % mo) % mo;
    dep = ((k-1) * dep + (dep+1) * m % mo) % mo * inv(k+m-1) % mo;
    k = k + (m-1);
  }
  std::cout << contri;



  return 0;
}