#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

string to_string(string a) { return '"' + a + '"'; }
string to_string(char a) { return "'" + string(1, a) + "'"; }
string to_string(const char* a) { return to_string((string) a); }
string to_string(bool a) { return a ? "true" : "false"; }
template <class T1, class T2>
string to_string(pair<T1, T2> a) {
    return "(" + to_string(a.first) + ", " + to_string(a.second) + ")";
}
template <class T>
string to_string(T a) {
    bool first = true; string res = "{";
    for (const auto& i : a) {
        if (!first) res += ", ";
        first = false;
        res += to_string(i);
    }
    res += "}";
    return res;
}
void debug_out() { cerr << endl; }
template <class T1, class... T2>
void debug_out(T1 a, T2... b) {
    cerr << " " << to_string(a);
    debug_out(b...);
}

#ifdef LOCAL
#define out(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define out(...) 42
#endif

const int mod = 1e9 + 9;

int add(int a, int b) {
    return a + b >= mod ? a + b - mod : a + b;
}

int sub(int a, int b) {
    return a - b < 0 ? a - b + mod : a - b;
}

int mult(int a, int b) {
    return int(1ll * a * b % mod);
}

int binpow(int a, int n) {
    int res = 1;
    for (; n >= 1; n >>= 1) {
        if (n & 1) res = mult(res, a);
        a = mult(a, a);
    }
    return res;
}

int inv(int a) {
    return binpow(a, mod - 2);
}

#define div my_div

int div(int a, int b) {
    return mult(a, inv(b));
}

const int N = 1e7 + 10;
int f[N];

int fact[N], inv_fact[N];

void init() {
    fact[0] = 1;
    for (int i = 1; i <= N - 1; i++) {
        fact[i] = mult(fact[i - 1], i);
    }
    inv_fact[N - 1] = inv(fact[N - 1]);
    for (int i = N - 2; i >= 0; i--) {
        inv_fact[i] = mult(inv_fact[i + 1], i + 1);
    }
}

int C(int n, int k) {
    if (n < 0 || k < 0 || n < k) {
        return 0;
    } else {
        return mult(fact[n], mult(inv_fact[k], inv_fact[n - k]));
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif

    // init();

    int m, k;
    cin >> m >> k;
    f[0] = 0;
    int ans = 0;
    int tot = 1;
    for (int i = 1; i <= k; i++) {
        ans = add(ans, mult(add(f[i - 1], 1), m)); // (f[i - 1] + 1) * m
        tot = add(tot, m - 1);
//        int inv_tot = inv(tot);
//        f[i] = add(mult(mult(m, inv_tot), add(f[i - 1], 1)), mult(mult(sub(tot, m), inv_tot), f[i - 1]));
        f[i] = add(f[i - 1], div(m, tot));
    }
    cout << ans << "\n";

#ifdef LOCAL
    cout << "\nTime elapsed: " << double(clock()) / CLOCKS_PER_SEC << " s.\n";
#endif
}