#include<bits/stdc++.h>

#define endl '\n'
using i64 = long long;
constexpr i64 MOD = 1e9 + 9;

i64 binpow(i64 a, i64 b) {
    i64 res = 1;
    while (b) {
        if (b & 1) res = (res * a) % MOD;
        a = (a * a) % MOD;
        b >>= 1;
    }
    return res;
}

void solve() {
    i64 m, k;
    std::cin >> m >> k;
    i64 d = 0, ans = 0;
    for (int i = 1; i <= k; i++) {
        ans = (ans + (d + 1) % MOD * m % MOD) % MOD;
        i64 sum = (i - 1) * (m - 1) % MOD;
        d = (sum * d % MOD + m * (d + 1) % MOD) * binpow(sum + m, MOD - 2) % MOD;
    }
    std::cout << ans << '\n';
}

int main() {
    std::ios::sync_with_stdio(false), std::cin.tie(nullptr);
    int CZY = 1;
//    std::cin >> CZY;
    while (CZY--)solve();
}