#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define maxn 10000005
#define mod 1000000009

int64_t qpow(int64_t a, int64_t x) {
    int64_t ans = 1;
    while (x) {
        if (x & 1) ans = ans * a % mod;
        a = a * a % mod, x >>= 1;
    }
    return ans;
}
int64_t inv(int64_t a) { return qpow(a, mod - 2); }

void solve(void) {
    int m, k;
    cin >> m >> k;
    int64_t ans = 1, f = 1;
    for (int i = 2; i <= k; i++)
        f = (f + m * inv(1 + (i - 1) * (m - 1))) % mod, ans = (ans + f) % mod;
    cout << ans * m % mod << endl;
    return;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    int _ = 1;
    while (_--) solve();

    return 0;
}