#include <bits/stdc++.h>
using namespace std;
const int N = 1e7 + 10;
const int p = 1e9 + 9;
int m, k;
int h[N], hinv[N], hfac[N], g[N], f[N];
inline int Qpow(int x, int y = p - 2) {
    int ans = 1;
    for (; y; y >>= 1, x = 1ll * x * x % p) 
        if (y & 1) ans = 1ll * ans * x % p;
    return ans;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> m >> k;
    h[0] = 1; hfac[0] = 1; 
    for (int i = 1; i <= k; ++i) {
        h[i] = (h[i - 1] + m - 1) % p;
        hfac[i] = 1ll * hfac[i - 1] * h[i] % p;
    }
    hinv[0] = 1;
    for (int i = k, val = Qpow(hfac[k]); i; --i) {
        hinv[i] = 1ll * hfac[i - 1] * val % p;
        val = 1ll * val * h[i] % p;
    }
    int ans = 0;
    for (int i = 1; i <= k; ++i) {
        int val = 1ll * g[i - 1] * hinv[i - 1] % p;
        ans = (ans + 1ll * (val + 1) * m) % p;
        g[i] = (g[i - 1] - val + 1ll * (val + 1) * m) % p;
    }
    if (ans < 0) ans += p;
    cout << ans << endl;
    return 0;
}