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

int read(){
	int f=0,s=0; char c=getchar();
	while(c>'9'||c<'0')f=(c=='-'),c=getchar();
	while(c>='0'&&c<='9')s=(s<<3)+(s<<1)+(c^'0'),c=getchar();
	return f?-s:s;
}

const int N=1e7+5;
const int mod=1e9+9;
int m,k;
int f,g;
int ksm(int a,int b=mod-2){
	int res=1;
	for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)res=1ll*res*a%mod;
	return res;
}

int main(){
	m=read(); k=read();
	f=g=0;
	// int tm1=clock();
	int cnt=1;
	for(int i=1;i<=k;i++){
		int tf=f,tg=g;
		int tcnt=ksm(cnt);
		int tmp=1ll*tg*tcnt%mod;
		f=(1ll*m*(1+tmp)%mod+tf)%mod;
		cnt+=m-1;
		g=(m+1ll*cnt*tcnt%mod*tg%mod)%mod;
	}
	cout<<f<<endl;
	// int tm2=clock();
	// cout<<1.0*(tm2-tm1)/CLOCKS_PER_SEC;
	return 0;
}