#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
using ll = long long;
const int mod = 1e9 + 9;

int add(int a, int b) {
    int c = a + b;
    if (c >= mod) c -= mod;
    return c;
}
int sub(int a, int b) {
    int c = a - b;
    if (c < 0) c += mod;
    return c;
}
int mul(int a, int b) {
    ll c = 1ll * a * b;
    if (c >= mod) c %= mod;
    return c;
}
inline int ksm(int a, int b) {
    int res = 1;
    for (; b; b >>= 1) {
        if (b & 1) {
            res = 1ll * res * a % mod;
        }
        a = 1ll * a * a % mod;
    }
    return res;
}

const int N = 10000010;
int f[N], cnt[N], inv[N], prod[N], iprod[N];

void solve() {
    int M, K; cin >> M >> K;
    cnt[0] = 1;
    for (int i = 1; i <= K; ++i) cnt[i] = cnt[i - 1] + M - 1;
    prod[0] = 1;
    for (int i = 1; i <= K; ++i) prod[i] = mul(prod[i - 1], cnt[i]);
    iprod[K] = ksm(prod[K], mod - 2);
    for (int i = K - 1; i >= 1; --i) iprod[i] = mul(iprod[i + 1], cnt[i + 1]);
    for (int i = 1; i <= K; ++i) inv[i] = mul(prod[i - 1], iprod[i]);
    int ans = 0;
    f[0] = 0;
    for (int i = 1; i <= K; ++i) {
        cnt[i] = cnt[i - 1] + M - 1;
        int res = mul(M, add(mul(f[i - 1], inv[i - 1]), 1));
        ans = add(ans, res);
        f[i] = 0;
        f[i] = add(f[i], res);
        f[i] = add(f[i], f[i - 1]);
        f[i] = sub(f[i], mul(f[i - 1], inv[i - 1]));
    }
    cout << ans << endl;
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}