#include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
template <typename T> void qmin(T &x,T y) { x=min(x,y); }
template <typename T> void qmax(T &x,T y) { x=max(x,y); }
typedef pair<int,int> pii;
const int mod=1e9+9;
const int maxn=1e7+10;
int inf=1e18;
int de=0;
int n,m,k;
int leafsum[maxn],leaf[maxn],sum[maxn];
int qpow(int x,int y)
{
	int ans=1,base=x;
	while(y)
	{
		if(y&1)
		{
			ans*=base;
			ans%=mod;
		}
		base*=base;
		base%=mod;
		y>>=1;
	}
	return ans;
}
int ny(int x)
{
	return qpow(x,mod-2);
}
int add(int x,int y){
    x+=y; x%=mod;
    return x;
}
int del(int x,int y){
    x-=y; x%=mod; x+=mod; x%=mod;
    return x;
}
int mul(int x,int y){
    x*=y; x%=mod;
    return x;
}
void solve(){
    cin>>m>>k;
    for(int i=1;i<=k;i++){
        leafsum[i]=add(del(leafsum[i-1],leaf[i-1]),mul(m,leaf[i-1]+1));
        leaf[i]=mul(leafsum[i],ny(1+(m-1)*i));
        sum[i]=add(sum[i-1],mul(leaf[i-1]+1,m));
    }
    cout<<sum[k]<<"\n";
}
signed main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int TT;
    TT=1;
    //cin>>TT;
    while(TT--){
        solve();
    }
    return 0;
}