#include <bits/stdc++.h>

const int mod = 1e9 + 9;

int qpow(int base, int b, int ret = 1) {
    for (; b; base = 1ll * base * base % mod, b >>= 1)
        if (b & 1)
            ret = 1ll * ret * base % mod;
    return ret;
}

int main() {
    int m, k;
    std::cin >> m >> k;
    std::vector<int> fac(k + 1), inv(k + 1);
    fac[0] = inv[0] = 1;
    for (int i = 1; i <= k; ++i) {
        fac[i] = 1ll * fac[i - 1] * (1ll * i * (m - 1) % mod + 1) % mod;
    }
    inv[k] = qpow(fac[k], mod - 2);
    for (int i = k - 1; i >= 1; --i) {
        inv[i] = 1ll * inv[i + 1] * (1ll * (i + 1) * (m - 1) % mod + 1) % mod;
    }
    for (int i = 1; i <= k; ++i) {
        inv[i] = 1ll * inv[i] * fac[i - 1] % mod;
    }
    int sum = 0, ans = 0;
    for (int i = 0; i < k; ++i) {
        int exp = 1ll * sum * inv[i] % mod;
        (sum += 1ll * (1ll * (exp + 1) * m % mod + mod - exp) % mod) %= mod;
        (ans += 1ll * (exp + 1) * m % mod) %= mod;
        // std::cout << sum << ' ' << inv[i] << std::endl;
    }
    std::cout << ans << std::endl;
    return 0;
}