#include<bits/stdc++.h>

using i64 = long long;

const int mod = 1000000009;

i64 ksm (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 a = 1, n = m;
    i64 ans = m;
    for(int i = 1; i < k; i++) {
        ans = (ans + (a + 1) * m % mod) % mod;
        a = ((n - 1+mod)%mod * a % mod + (a + 1)%mod * m%mod)%mod;
        n = (n - 1 + m) % mod;
        a = a * ksm(n, mod - 2) % mod;
    }
    std::cout << ans << '\n';
}  

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);   
    std::cin.tie(0);

    i64 t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}