#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

void solve() {
    constexpr int mod = 1e9+9;
    function<int(int, int)> qmi = [&] (int a, int b) {
        int res = 1;
        while (b) {
            if (b & 1) res = 1ll * res * a % mod;
            a = 1ll * a * a % mod;
            b >>= 1;
        }
        return res;
    };
    int m, k; cin >> m >> k;
    int e = 0, lst = 1;
    i64 ans = 0;
    // vector<int> fac(k + 1);
    // fac[0] = 1;
    // for (int i = 1; i <= k; i ++ ) 
    //     fac[i] = 1ll * fac[i - 1] * i % mod;
    // vector<int> inv(k + 1); 
    // inv[k] = qmi(fac[k], mod - 2);
    // for (int i = k; i; i -- )
    //     inv[i - 1] = 1ll * i * inv[i] % mod;
    //int base = qmi(m, mod - 2);
    for (int i = 1; i <= k; i ++ ) {
        e = 1ll * e * qmi(lst, mod - 2) % mod;
        int res = 1ll * (e + 1) * m % mod;
        ans = (ans + res) % mod;
        e = (1ll * e * (lst - 1) % mod + res) % mod;
        lst += m - 1; 
    }
    //cerr << 1ll * 34 * qmi(3, mod - 2) % mod << "\n";
    cout << ans << "\n";
}

int main (void) {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T = 1;
    while (T -- ) solve();
    return 0;
}