#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int p = 1e9+9;
const int N = 1e7+5;
#define pb push_back
int m, k;
ll pm, A[N], g, f[N];

ll qpow(ll a, ll b)
{
  ll ans = 1;
  while(b)
  {
    if(b & 1)ans = (ans * a) % p;
    a = (a * a) % p;
    b >>= 1;
  }
  return ans;
}  

// ll f(int x)
// {
//   if(x == 0)return 0;
//   x--;
//   ll pmn;
//   if(x > 0) pmn = (1LL * qpow(A[x], p-2) * A[x-1]) % p;
//   else pmn = 1;
//   ll ans = 1LL * qpow(m, 2) * pm % p + (1LL * (1 + 1LL * (m-1) * pmn % p) * f(x)) % p;
//   return ans % p;
// }

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  cin >> m >> k;
  if(m == 1)
  {
    ll ans = 1LL * k * (k + 1) / 2 % p;
    cout << ans << '\n';
    return 0;
  }
  pm = qpow(m-1, p-2);
  A[0] = 1;
  for(int i = 1; i <= k; ++i)
  {
    A[i] = ((1LL * A[i-1] * ((1 + 1LL * (m-1) * i % p) % p)) % p) % p;
  }
  f[0] = 0;
  for(int i = 1; i <= k; ++i)
  {
    ll pmn;
    int x = i-1;
    if(x > 0) pmn = (1LL * qpow(A[x], p-2) * A[x-1]) % p;
    else pmn = 1;
    f[i] = 1LL * qpow(m, 2) * pm % p + (1LL * (1 + 1LL * (m-1) * pmn % p) * f[x]) % p;
    f[i] = f[i] % p;
  }

  ll g = 1LL * ((1LL * k * m) % p) * pm % p;
  ll ans = ((f[k] - g) % p + p) % p;

  cout << ans << '\n';


}