#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int ret=0,flg=0;
	char c=getchar();
	while(c<'0'||c>'9')flg|=c=='-',c=getchar();
	while(c>='0'&&c<='9')ret=(ret<<3)+(ret<<1)+c-'0',c=getchar();
	return flg?-ret:ret;
}
inline void write(int x,bool flg){
	char a[21];
	if(!x)putchar('0');
	if(x<0)putchar('-'),x=-x;
	int cnt=0;
	while(x){
		a[++cnt]=x%10+'0';
		x/=10;
	}
	while(cnt)putchar(a[cnt--]);
	putchar(flg?'\n':' ');
	return ;
}
const int mod =1e9 +9;
inline int qpow(int x,int y){
	int ret=1,p=x;
	while(y){
		if(y&1)ret=1ll*ret*p%mod;
		y>>=1;
		p=1ll*p*p%mod;
	}return ret;
}
int main(){
	int n=1,sum=0,l=1,d=0,m=read(),k=read();
	for(int i=1;i<=k;i++){
		sum=(sum+1ll*(d+1)*m)%mod;
		d=(1ll*l*d+1ll*(m-1)*(d)+m)%mod*qpow((l+m-1)%mod,mod-2)%mod;
		n=(n+m)%mod;
		l=(l+m-1);
	}write(sum,1);
	return 0;
}