#include<bits/stdc++.h>
using namespace std;
#define V vector
#define pb push_back
typedef pair<int, int> pi;
typedef long long LL;
#define fi first
#define se second

const int mod = 1e9 + 9;
LL qpow(LL x, LL k) {
    LL ans = 1;
    while(k) {
        if(k & 1) ans = ans * x % mod;
        k /= 2;
        x = x * x % mod;
    }
    return ans;
}
int main() {
    int m, k; cin >> m >> k;
    //-> hav = 1 + m * (i - 1);
    //LL sum = ? 
    //LL new = sum / hav
    //sum' = sum + new * m;
    int hav = 1;
    LL sum = 0;
    LL ans = 0;
    for(int i = 1; i <= k; i++) {
        LL avg = (qpow(hav, mod - 2) * sum) % mod;
        sum = (sum + avg * (m - 1) + m) % mod;
        ans = (ans + (avg + 1) * m) % mod;
        hav += m - 1;
    }
    cout << ans << endl;
    //0 -> 111111(1 * 6)
    //6 + (1 / 7) * (6) + (6 / 7) * (12)
}