#include <bits/stdc++.h>
#define fep(A,B,C) for(int C=A;C>=B;--C)
#define rep(A,B,C) for(int C=A;C<=B;++C)
#define ll long long
using namespace std;
const int MAXN=10000010;
#define mod 1000000009
int n,k,m;
int f[MAXN],g[MAXN];
int w[MAXN];
int ksm(int b,int p)
{
	int cnt=1;
	while(p)
	{
		if(p&1)cnt=(ll)cnt*b%mod;
		b=(ll)b*b%mod;p=p>>1;
	}
	return cnt;
}
int main()
{
	//freopen("1.in","r",stdin);
	scanf("%d%d",&m,&k);
	w[k+1]=1;
	fep(k,0,i)
	{
		w[i]=(ll)((m-1)*i+1)*w[i+1]%mod;
	}
	int cc=ksm(w[0],mod-2);
	f[0]=0;g[0]=0;
	//f为叶子节点的深度期望
	//g为所有节点总期望
	rep(1,k,i)
	{
		int sz=(i-1)*m+1;
		int yz=sz-i+1;
		
		int nex=yz+m-1;
		f[i]=(f[i-1]+(ll)m*cc%mod*w[i+1])%mod;
		
		g[i]=(g[i-1]+(ll)m*(f[i-1]+1))%mod;

		cc=(ll)cc*((m-1)*i+1)%mod;

		//cout<<f[i]<<' '<<g[i]<<endl;
	}
	printf("%d\n",g[k]);
	return 0;
}