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

#define ll long long
const ll N = 1e7+10;
const ll mod=1e9+9;

ll m,k;
ll f[N],g[N],s[N],h[N];
ll fs[N];

ll qmi(ll k,ll p,ll m){
    ll res=1,a=k;
    while(p){
        if(p&1) res=res*a%m;
        a=a*a%m;
        p=p>>1;
    }
    return res;
}

int main(){
    cin>>m>>k;
    s[0]=1;
    fs[0]=1;
    for(int i=1;i<=k;++i){
      s[i]=(1+i*(m-1))%mod;
      fs[i]=qmi(s[i],mod-2,mod);
    } 
    for(int i=1;i<=k;i++){
        g[i]=(g[i-1]+(m*(s[i-1]+g[i-1]+i-1+mod)%mod-g[i-1]+mod)%mod*fs[i-1]%mod)%mod;
        g[i+1]=(g[i]+(m*(s[i]+g[i-1])%mod-g[i]+mod)%mod*fs[i]%mod)%mod;
    }
    cout<<g[k]<<endl;
    return 0;
}