#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
typedef long long LL;
const int INF = 0x3f3f3f3f3f3f3f3f, mod = 1e9 + 9;

bool multi = 0;

long long qpow(long long a,long long b,long long p){
    a%=p;
    long long res=1%p;
    while(b){
        if(b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}

void solve(){
    int m, k;
    cin >> m >> k;
    vector<int> f(k + 1), dp(k + 1);
    f[0] = 1;
    int ans = 0;
    for(int i = 1; i <= k; i++) {
        f[i] = (f[i - 1] - 1 + m) % mod;
        dp[i] = (dp[i - 1] + m * qpow(f[i], mod - 2, mod)) % mod;
        ans = (ans + (dp[i - 1] + 1) * m) % mod;
    }
    cout << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T = 1;
    if(multi) cin >> T;
    while(T--) {
        solve();
    }

    return 0;
}