#include<bits/stdc++.h>
using namespace std;

using ll = long long int;

const ll mod = 1e9+9;
const int nmax = 1e7+10;

ll leafcount[nmax];
ll e_leaf[nmax];

ll modexpo(ll x, ll n){
    ll ret = 1;
    while(n){
        if(n&1) ret = ret * x % mod;
        x = x * x % mod;
        n /= 2;
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

//    cout<<84 * modexpo(5, mod-2) % mod <<endl;

    ll m, k;
    cin>>m>>k;

    leafcount[0] = 1;
    e_leaf[0] = 0;

    ll ans = 0;

    for(int i = 1; i<=k; i++){
        leafcount[i] = leafcount[i-1] + (m-1);

        ans += (e_leaf[i-1] + 1) * m;
        ans %= mod;

        e_leaf[i] = (e_leaf[i-1] * (leafcount[i-1] - 1) + (e_leaf[i-1] + 1) * m) % mod
        ;
        e_leaf[i] = e_leaf[i] * modexpo(leafcount[i], mod-2) % mod;
    }

    cout<<ans<<endl;

}