#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 9;
const ll MAXN = 1e7 + 5;
ll m, k, E[MAXN], f[MAXN], invf[MAXN], inv[MAXN];
ll fastPow(ll a, ll b){
    ll ret = 1;
    while(b){
        if(b & 1) ret = ret * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> m >> k;
    ll ans = 0;
    f[0] = 1;
    for(int i = 1; i <= k; i ++){
        f[i] = f[i - 1] * ((i * (m - 1) + 1) % MOD) % MOD;
    }
    invf[k] = fastPow(f[k], MOD - 2);
    for(int i = k - 1; i >= 1; i --){
        invf[i] = invf[i + 1] * ((i + 1) * (m - 1) + 1) % MOD;
    }
    inv[0] = invf[0] = 1;
    for(int i = 1; i <= k; i ++){
        inv[i] = invf[i] * f[i - 1] % MOD;
    }
    for(int i = 1; i <= k; i ++){
        E[i] = (E[i - 1] * inv[i - 1] % MOD * ((i * (m - 1) + 1) % MOD) % MOD + m) % MOD;
        ans = (ans + (i == k ? E[i] : E[i] * inv[i])) % MOD;
        // cout << E[i] << "\n";
    }
    cout << ans << "\n";
    return 0;
}