#include <bits/stdc++.h>

using i64 = long long;

constexpr int P = 1E9 + 9;
constexpr int N = 1E7 + 1;
int pre[N], inv[N], E[N];

int norm(int x) {
    if (x >= P) {
        x -= P;
    } else if (x < 0) {
        x += P;
    }
    return x;
}

int power(int x, int exp) {
    int ans = 1;
    x = norm(x);
    while (exp > 0) {
        if (exp % 2) {
            ans = 1LL * ans * x % P;
        }
        x = 1LL * x * x % P;
        exp /= 2;
    }
    return ans;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int M, K;
    std::cin >> M >> K;

    inv[0] = pre[0] = 1;
    for (int i = 1; i < N; i++) {
        pre[i] = 1LL * pre[i - 1] * ((M - 1LL) * i % P + 1) % P;
    }

    int suf = power(pre[N - 1], P - 2);
    for (int i = N - 1; i >= 1; i--) {
        inv[i] = 1LL * suf * pre[i - 1] % P;
        suf = 1LL * suf * ((M - 1LL) * i % P + 1) % P;
    }

    int ans = 0;
    E[0] = 0;
    for (int i = 1; i <= K; i++) {
        int E_dep = 1LL * E[i - 1] * inv[i - 1] % P;
        ans = norm(ans + (E_dep + 1LL) * M % P);
        E[i] = norm(norm(E[i - 1] + E_dep * (M - 1LL) % P) + M);
    }
    std::cout << ans << "\n";

    return 0;
}