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

typedef long long ll;

const ll mod = 1000000009;

ll m,k,sqr;


ll qpow(ll b, ll x){
    if(x==0) return 1;
    ll tmp = qpow(b,x/2);
    if(x&1) return tmp*tmp%mod*b%mod;
    else return tmp*tmp%mod; 
}

ll inv(ll x){
    return qpow(x%mod, mod-2);
}

ll invv[10000005];

ll calc(ll i){
    return sqr*invv[i]%mod;
}

ll diff[10000005];

int main(){
    // m=100; k=1e7;
    cin>>m>>k;
    diff[1] = m;
    sqr = m*m%mod;
    for(int i=2; i<=k; ++i) invv[i] = inv(ll(i-1)*(m-1)+1);
    for(int i=2; i<=k; ++i){
        diff[i] = (diff[i-1] + calc(i))%mod;
    }
    ll g = 0;
    for(int i=1; i<=k; ++i) {
        g+=diff[i];
        g%=mod;
    }
    cout<<g<<endl;
    return 0;
}