#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
	x=0;char ch=getchar();bool f=false;
	while(!isdigit(ch))	f|=ch=='-',ch=getchar();
	while(isdigit(ch))	x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=f?-x:x;return;
} 
template <typename T>
inline void print(T x){
	if(x<0)	putchar('-'),x=-x;
	if(x>9)	print(x/10);
	putchar(x%10^48);return; 
}
const int mod=1e9+9;
int ans;
int pre,now;
int cnt_p,cnt_n;
#define ll long long 
int m,k,p;
int power(int x,int y){
	int ans=1;
	while(y){
		if(y%2==1) ans=(long long)ans*x%mod;
		y/=2;
		x=(long long)x*x%mod;
	}
	return ans;
}
int main(){
	scanf("%d%d",&m,&k);
	int cnt=m;
	pre=0;
	ans=0;
	for(int i=1;i<=k;i++){
		now=((long long)m*power(cnt,mod-2)%mod+pre)%mod;
		ans=(ans+pre)%mod;
		pre=now;
		cnt=cnt+m-1;
	}
	ans=((long long)(cnt-m+1)*pre%mod+ans)%mod;
	printf("%d",ans);
	return 0;
}