#include <bits/stdc++.h>

const int64_t MOD = 1E9 + 9;

int64_t power(int64_t a, int64_t b, int64_t p) 
{
    int64_t res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

int64_t inv(int64_t a, int64_t p) 
{
    return power(a, p - 2, p);
}

void solve() 
{
    int m, k;
    std::cin >> m >> k;
    std::vector<int64_t> pinv(k), a(k + 1);
    for (int i = 1; i <= k; ++i) {
        int64_t num = (int64_t(m - 1) * (i - 1) % MOD + 1) % MOD;
        pinv[i - 1] = inv(num, MOD);
        a[i] = (((1 + (m - 1) * pinv[i - 1] % MOD) % MOD) * a[i - 1] % MOD + m) % MOD;
    }
    int64_t ans = 0;
    for (int i = 0; i < k; ++i) {
        ans = (ans + (a[i] * pinv[i] % MOD + 1) % MOD) % MOD;
    }
    ans = ans * m % MOD;
    std::cout << ans << '\n';
}   

int main() 
{
    std::cin.tie(nullptr)->std::ios::sync_with_stdio(false);
    
    int t = 1;
    while(t--) {
        solve();
    }
    
    return 0;
}