#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;
}

const int N = 10000010;
int ans[N], f[N], cnt[N];

void solve() {
    int M, K; cin >> M >> K;
    int ANS = 0;
    f[0] = 0;
    cnt[0] = 1;
    for (int i = 1; i <= K; ++i) {
        cnt[i] = cnt[i - 1] + M - 1;
        int inv = ksm(cnt[i - 1], mod - 2);
        ans[i] = mul(M, add(mul(f[i - 1], inv), 1));
        ANS = add(ANS, ans[i]); 
        f[i] = 0;
        f[i] = add(f[i], ans[i]);
        f[i] = add(f[i], f[i - 1]);
        f[i] = sub(f[i], mul(f[i - 1], inv));
        // cerr << "new = " << ans[i] << ", sum = " << f[i] << endl;
    }
    cout << 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;
}