#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+9;
int k,m,sum,ans;
int fp(int a,int b){
	int res=1;
	for(;b;b>>=1,a=1ll*a*a%mod)
		if(b&1)
			res=1ll*res*a%mod;
	return res;
}
const int N=1e7+11;
int a[N],b[N],c[N];
#define rep(i,s,t) for(int i=s;i<=t;++i)
int main(){
	scanf("%d%d",&m,&k);
	int sum=1;
	b[0]=1;
	rep(i,1,k-1){
		a[i]=(1ll*i*m-i+1)%mod;
		b[i]=1ll*b[i-1]*a[i]%mod;
	}
	int inv=fp(b[k-1],mod-2);
	c[k-1]=inv;
	for(int i=k-2;i>=0;--i){
		c[i]=1ll*c[i+1]*a[i+1]%mod;
	}
	sum=0;
	rep(i,1,k-1){
		a[i]=1ll*c[i]*b[i-1]%mod;
		sum=(sum+a[i])%mod;
		ans=(ans+sum)%mod;
	}
	ans=1ll*ans*m%mod*m%mod;
	ans=(ans+1ll*k*m)%mod;
	printf("%d\n",ans);
	return 0;
}