#include <bits/stdc++.h>

#define ll long long

const ll K = 1e7 + 5, mod = 1e9 + 9;

ll m, k, f[K], g[K], ans;

ll read() {
    ll res = 0, i = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') i = -i;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = getchar();
    }
    return res * i;
}

void write(ll x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int main() {
    m = read(), k = read();
    for (ll i = 1; i <= k; ++i)
        g[i] = qpow(((m - 1) * (i - 1) % mod + 1) % mod, mod - 2), f[i] = (((f[i - 1] + (m - 1) * f[i - 1] % mod * g[i] % mod) % mod + m) % mod) % mod;
    for (ll i = 1; i <= k; ++i)
        ans = (ans + (m * f[i - 1] % mod * g[i] + m) % mod) % mod;
    write(ans);
    return 0;
}