#include <bits/stdc++.h>
#define int int64_t

const int p = 1E9 + 9;
int binpow(int x, int k) {
  int res = 1;
  while(k) {
    if(k & 1) res = res * x % p;
    x = x * x % p;
    k >>= 1;
  }
  return res;
}

using std::cin;
using std::cout;
const char endl = '\n';
int g;
int f;

void solve() {
  int m, k;
  cin >> m >> k;
  for(int i = 0; i < k; ++i) {
    int tmp = g * binpow((i * (m - 1) % p + 1) % p, p - 2) % p;
    g = (g + m * (tmp + 1) % p - tmp + p) % p;
    f = (f + m * (tmp + 1) % p) % p;
    // cout << "de: " << g << " " << f << endl;
  }
  cout << f << endl;
}

int32_t main(){
#ifndef _DEBUG
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
#endif
  int tc = 1;
  // std::cin >> tc;
  while(tc--) solve();
#ifdef _DEBUG
  std::cout << std::endl;
  std::cout << "Time used: " << clock() << "ms" << std::endl;
  system("pause");
  return 0;
#endif
}