#include <bits/stdc++.h>

#define endl "\n"
#define int long long
using namespace std;

typedef pair<int,int> PII;
const int N = 10000000 + 5, MOD = 1e9 + 9;
int k, m;
PII a[N];
int dp[N], f[N];

int read(){
    int x = 0,f = 1;
    char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        x = (x << 1) + (x << 3) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int ksm(int a,int b){
    int r = 1;
    while (b){
        if (b & 1) r = r * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return r;
}

void solve(){
    cin >> m >> k;
    f[0] = 1;
    int ans = 0;
    for(int i = 1; i <= k; i++){
        f[i] = (f[i - 1] + m - 1) % MOD;
        dp[i] = ((dp[i - 1] * f[i] % MOD + m) % MOD * ksm(f[i], MOD - 2) % MOD) % MOD;
        ans = (ans + dp[i - 1] % MOD) % MOD;
    }
    cout << (ans + dp[k] * f[k] % MOD) % MOD;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int _ = 1;
    // cin >> _;
    while(_--){
        solve();
    }
}