#include <cassert>
#include <iostream>
#include <vector>
using namespace std;

const int mod = 1e9 + 9;
using ll = long long;
int qpow(int x, ll y) {
    ll ans = 1;
    for (; y; y >>= 1, x = 1ll * x * x % mod) {
        if (y & 1) ans = ans * x % mod;
    }
    return ans;
}
int inv(int x) {
    return qpow(x, mod - 2);
}
void sub(int& a, int b) {
    a = a >= b ? a - b : a + mod - b;
}
int main() {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
    int m, k;
    cin >> m >> k;
    ll F = 1;
    ll F1 = 0;
    ll ans = 0;
    for (int i = 0, tmp = 1; i < k; ++i, tmp += m - 1) {
        int k = 1ll * m * inv(tmp) % mod;
        int val = 1ll * (tmp + m - 1) * inv(tmp) % mod;
        ans += (F1 + F) * inv(tmp) % mod * m % mod;
        F1 = (F1 * val + F * k) % mod;
        F = F * val % mod;
        // cout << F1 << " " << F << '\n';
        // cout << (F1 + F) * inv(tmp) * m << '\n';
        // cout << '\n';
    }
    cout << ans % mod << '\n';
}