#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a),i##END=(b);i<=i##END;i++)
#define Rof(i,b,a) for(int i=(b),i##END=(a);i>=i##END;i--)
#define go(u) for(int i=head[u];i;i=nxt[i])
#define int long long
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=1e7+10,p=1e9+9;
inline int inv(int a,int b=p-2){
	int x=1;while(b){
		if(b&1)(x*=a)%=p;
		(a*=a)%=p,b>>=1;
	}return x;
}
int m,k;
int E[N],T[N],S[N];
signed main(){
	m=read(),k=read();
	S[0]=1;For(i,1,k)S[i]=S[i-1]+m-1;
	For(i,1,k){
		E[i]=T[i-1]+1;
		T[i]=(T[i-1]*(S[i-1]-1)+m*E[i])%p*inv(S[i])%p;
		// printf("E[%lld] = %lld, T[%lld] = %lld\n",i,E[i],i,T[i]);
	}
	int ans=0;
	For(i,1,k)(ans+=m*E[i])%=p;
	cout<<ans<<endl;
	return 0;
}