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

constexpr ll MOD = 1000000009;

ll pow_mod(ll x, ll n) {
  if(n==0) return 1;
  ll res = 1;
  while(n) {
    if(n&1) res = res*x%MOD;
    x=x*x%MOD;
    n>>=1;
  }
  return res;
}
ll pow_inv(ll x) {
  return pow_mod(x, MOD-2);
}


int main() {
  ll M, K; cin >> M >> K;
  ll ans = 0, e = 0, c = 1, cnt = 1;
  for(int k = 0; k < K; k++) {
    cnt *= c;
    cnt %= MOD;
    tie(c, e, ans) = make_tuple(c+M-1, e*c+e*(M-1)+M*cnt, ans*c+e*M+M*cnt);
    c %= MOD;
    e %= MOD;
    ans %= MOD;
  }
  ans *= pow_mod(cnt, MOD-2);
  ans %= MOD;
  cout << ans << '\n';
}