//
// Created by DELLPC on 2024/3/9.
//
#include<bits/stdc++.h>

#define irep(i, l, r) for(int i = l; i <= r; ++ i)

const int mod = 1000000000 + 9;

using namespace std;

#define ll long long

ll qpow(ll base, ll b) {
    ll ans = 1;
    while(b) {
        if(b & (1)) {
            ans *= base, ans %= mod;
        }
        base *= base, base %= mod, b >>= 1;
    }
    return ans;
}

ll inv(ll x) {
    return qpow(x, mod - 2 );
}

int main() {
    ll m, k;
    ll E0 = 0;
    cin >> m >> k;
    ll ans = 0;
    irep(n, 0, k - 1) {
        // cerr << E0 << endl;
        ans += m * (E0 + 1), ans %= mod;
        ll E1 = E0 * (m - 1) % mod * n  + (E0 + 1) * m;
        E1 %= mod;
        E1 *= inv(((m - 1) * (n + 1) + 1) % mod);
        E1 %= mod;
        E0 = E1;
    }
    cout << ans % mod;
    return 0;
}