#include <bits/stdc++.h>
using ll = long long;
using lb = long double;
const int mod = 1e9 + 9;

ll ksm(ll a, ll b) {
    ll ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % mod;
        b = b >> 1;
        a = a * a % mod;
    }
    return ans;
}

void solve() {
    ll m, k; std::cin >> m >> k;
    std::vector<ll> f(k + 1);
    ll num = 1, ans = 0;
    for(ll i = 1; i <= k; i++) {
        ans = (ans + f[i - 1]) % mod;
        num = (num - 1 + m) % mod;
        f[i] = (f[i - 1] * num % mod + m) % mod * ksm(num, mod - 2) % mod;
        // f[i] = (f[i - 1] * num + m) * 1.0 / num;
        // std::cout << i << ' ' << f[i] << ' ' << num << '\n';
    }
    ans = ((ans + f[k] * num % mod) % mod + mod) % mod;
    std::cout << ans << '\n';
}

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