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

typedef long long ll;

const ll mod = 1000000009;

ll m,k;


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 calc(ll i){
    return (m*m)%mod*inv((i-1)*(m-1)+1);
}

ll diff[10000005];

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