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

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

ll m,k;
ll f[N],g[N],s[N],h[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;
    for(int i=1;i<=k;i++) s[i]=(1+i*(m-1))%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*qmi(s[i-1],mod-2,mod)%mod)%mod;
        g[i+1]=(g[i]+(m*(s[i]+g[i-1])%mod-g[i]+mod)%mod*qmi(s[i],mod-2,mod)%mod)%mod;
    }
    cout<<g[k]<<endl;
    return 0;
}