#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
// #define int long long
using ll = long long;
const int mod = 1e9 + 9;

int add(int a, int b) {
    int c = a + b;
    if (c >= mod) c -= mod;
    return c;
}
int sub(int a, int b) {
    int c = a - b;
    if (c < 0) c += mod;
    return c;
}
int mul(int a, int b) {
    ll c = 1ll * a * b;
    if (c >= mod) c %= mod;
    return c;
}
inline ll ksm(ll a, ll b) {
    ll res = 1;
    for (; b; b >>= 1) {
        if (b & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
    }
    return res;
}
inline ll inv(int x) {
    return ksm(x, mod - 2);
}
inline ll frac(int x, int y) { // x / y (mod)
    return 1ll * x * inv(y) % mod;
}

int m, k;
void solve() {
    cin >> m >> k;
    int all = 0, cnt = 1;
    int res = 0, ans = 0;
    for(int i = 1; i <= k; i++) {
        int v = frac(all, cnt);
        res = sub(all, v);
        ans = add(v, ans);
        all = add(res , mul((v + 1), m));
        cnt += m - 1;
    }
    cout << add(all, ans) << endl; 
}
/*

*/
signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}