#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 9;

/*
    o
   /|\
  o o o
K = 1, {1,3}
K = 2, {1,6} or {1,3,3} * 3
K = 3, {1,9} or {1,6,3} * 3 or {1,3,3,3} *   
*/

ll qpow(ll x,ll y){
    x %= MOD;
    ll ans = 1;
    while(y){
        if(y & 1)ans = ans * x % MOD;
        x = x * x % MOD;
        y >>= 1;
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll m,k;
    cin >> m >> k;
    ll ans = 0;
    ll h = 0;
    for(ll i = 0;i < k;++i){
        ll ah = m * (h + 1) % MOD;
        ans = (ans + ah) % MOD;
        h = (i * (m - 1) % MOD * h % MOD + ah) % MOD;
        h = h * qpow(i * (m - 1) % MOD + m,MOD-2) % MOD;
    }
    cout << ans << '\n';
    return 0;
}