#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=10000010,mod=1000000009;
int M,K,n[maxn],f[maxn],g[maxn],ni[maxn];

int qp(int a,int b)
{
	int res=1;
	for (;b;b>>=1)
	{
		if (b&1)
			res=1ll*res*a%mod;
		a=1ll*a*a%mod;
	}
	return res;
}

int inc(int a,int b)
{
	a+=b;
	if (a>=mod)
		a-=mod;
	return a;
}

int main()
{
	scanf("%d%d",&M,&K);
	for (int i=1;i<=K;i++)
		n[i]=1+(M-1)*i,ni[i]=qp(n[i],mod-2);
	n[0]=ni[0]=1;
	for (int i=1;i<=K;i++)
	{
		f[i]=inc(1ll*inc(1ll*f[i-1]*ni[i-1]%mod,1)*M%mod,1ll*f[i-1]*ni[i-1]%mod*inc(n[i-1],mod-1)%mod);
		g[i]=inc(g[i-1],1ll*f[i-1]*ni[i-1]%mod);
	}
	printf("%d\n",inc(f[K],g[K]));
	return 0;
}