#include <bits/stdc++.h>
using i80 = __int128;
using i64 = long long;
using f80 = long double;
constexpr i64 mod = 1e9 + 9;
i64 pw(i64 x, i64 k) {
    i64 z = 1;
    while (k) {
        if (k & 1) {
            z = z * x % mod;
        }
        x = x * x % mod;
        k >>= 1;
    }
    return z;
}
i64 inv(i64 x) {
    return pw(x, mod - 2);
}
void work() {
    int m, k;
    std::cin >> m >> k;
    i64 cnt = 0, sum = 0, tmp;
    for (int i = 1; i <= k; ++i) {
        tmp = inv(((m - 1) * (i - 1) + 1) % mod);
        sum = (sum + cnt * m % mod * tmp + m) % mod;
        cnt = (cnt * ((m - 1) * i % mod + 1) % mod * tmp % mod + m) % mod;
    }
    std::cout << sum << "\n";

    return;
}
void init() {
}
int main() {
    init();
    std::ios::sync_with_stdio(false);
    // std::cin.tie(nullptr), std::cout.tie(nullptr);
    int t = 1;
    // std::cin >> t;
    while (t--) {

        work();
    }

    return 0;
}
/*


*/