#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll p = 1e9+9;
ll qpow(ll a,ll n)
{
    ll ans = 1;
    while(n)
    {
        if(n&1) ans = (ans*a)%p;
        a = (a*a)%p;
        n>>=1;
    }
    return ans;
}
const int maxn = 1e7+5;
ll s[maxn],sv[maxn],inv[maxn];
ll E2[maxn];
void mod(ll & x)
{
    if(x>=p) x-=p;
    else if(x<0) x+=p;
}
//(m-1)(x-1)+1 for x = 1 到 k.
void init(int m,int k)
{
    s[0] = 1;
    for(int i = 1;i<=k;i++)
    {
        ll curval = 1ll*(m-1)*(i-1)+1;
        s[i] = (s[i-1]*curval)%p;
    }
    sv[k] = qpow(s[k],p-2);
    for(int i = k;i>=1;i--)
    {
        ll curval = 1ll*(m-1)*(i-1)+1;
        sv[i-1] = (sv[i]*curval)%p;
    }
    for(int i = 1;i<=k;i++) inv[i] = (sv[i]*s[i-1])%p;
    //i次操作后的叶子深度和期望   
    E2[0] = 0;
    for(int i = 1;i<=k;i++)
    {
        E2[i] = (1ll*(m-1)*i+1)*inv[i]%p*E2[i-1]%p;
        E2[i]+=m;
        mod(E2[i]);
    }
    ll ans = 0;
    //每次操作的贡献:上一次操作后的叶子深度和预期 / 叶子数目 = avg深度
    for(int i = 1;i<=k;i++)
    {
        ll del = E2[i-1]*inv[i]%p;
        del++;mod(del);
        del = (del*m)%p;
        ans+=del;
        mod(ans);
    }
    cout<<ans<<'\n';
}
void solve()
{    
    
    int m,k;cin>>m>>k;
    init(m,k);
    for(int i = 1;i<=k;i++)
    {

    }
}

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