#include<bits/stdc++.h>

using namespace std;

#define int long long

constexpr int P = 1e9 + 9;

int ksm(int x, int k) {
    int res = 1;
    while (k) {
        if (k & 1) res = res * x % P;
        x = x * x % P;
        k >>= 1;
    }
    return res;
}

void solve() {
    int m, k;
    cin >> m >> k;

    int x = 0, ans = 0, cnt = 1;
    for (int i = 1; i <= k; i++) {
        ans = (ans + (x + 1) * m % P) % P;
        int y = x;
        x = x * (cnt - 1) % P;
        x = (x + m * (y + 1) % P) % P;
        cnt = (cnt + m - 1) % P;
        x = x * ksm(cnt, P - 2) % P;
    }

    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;

    while (T--) {
        solve();
    }

    return 0;
}