#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)
#ifdef CKISEKI
#include <experimental/iterator>
#define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(auto s, auto ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int f = 0;
  (..., (cerr << (f++ ? ", " : "") << a));
  cerr << ")\e[0m\n";
}
void orange_(auto s, auto L, auto R) {
  cerr << "\e[1;33m[ " << s << " ] = [ ";
  using namespace experimental;
  copy(L, R, make_ostream_joiner(cerr, ", "));
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

using lld = int64_t;
const int mod = 1000000009;
int add(int a, int b) {
  return a + b >= mod ? a + b - mod : a + b;
}
int sub(int a, int b) {
  return a - b < 0 ? a - b + mod : a - b;
}
int mul(lld a, lld b) {
  return static_cast<int>(a * b % mod);
}

int modpow(int e, int p) {
  int r = 1;
  while (p) {
    if (p & 1) r = mul(r, e);
    e = mul(e, e);
    p >>= 1;
  }
  return r;
}

int modinv(int x) {
  return modpow(x, mod - 2);
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int M, K;
  cin >> M >> K;

  vector<int> cnt(K + 1), leaf(K + 1);
  int ans = 0;
  cnt[0] = 1;
  for (int i = 1; i <= K; i++) {
    cnt[i] = cnt[i - 1] + (M - 1);
  }

  vector<int> pre(K + 1), invcnt(K + 1);
  pre[0] = 1;
  for (int i = 1; i <= K; i++)
    pre[i] = mul(pre[i - 1], cnt[i]);

  int iv = modinv(pre[K]);
  for (int i = K; i >= 1; i--) {
    invcnt[i] = mul(iv, pre[i - 1]);
    iv = mul(iv, cnt[i]);
  }

  for (int i = 1; i <= K; i++) {
    leaf[i] = add(mul(mul(leaf[i - 1], invcnt[i - 1]), M - 1), M);
    leaf[i] = add(leaf[i], leaf[i - 1]);

    ans = add(add(mul(mul(leaf[i - 1], invcnt[i - 1]), M), M), ans);
  }

  cout << ans << '\n';

  return 0;
}