#include "bits/stdc++.h"

using namespace std;

const int mod = (int) 1e9 + 9;

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

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

int mul(int x, int y) {
    return x * 1ll * y % mod;
}

int binpow(int x, int n) {
    int res = 1;
    while (n) {
        if (n & 1) {
            res = mul(res, x);
        }
        x = mul(x, x);
        n >>= 1;
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int m, k;
    cin >> m >> k;
    int cnt = 1, ans = 0, e = 0;
    for (int i = 0; i < k; i++) {
        int res = mul(e + 1, m);
        ans = add(ans, res);
        e = add(mul(e, cnt - 1), res);
        cnt += m - 1;
        e = mul(e, binpow(cnt, mod - 2));
    }
    cout << ans << '\n';
}