#include<bits/stdc++.h>
#define f(i,x,y) for(int i=x;i<=y;i++)
#define df(i,x,y) for(int i=x;i>=y;i--)
#define int long long
#define pb push_back
using namespace std;
const int N=1.1e7,P=1e9+9;
int n,f[N],x,y,m,k,g[N],t=1;
int qp(int u,int v)
{
	int e=1;
	while(v)
	{
		if(v & 1)e = e * u % P;
		u = u * u % P;v /= 2;
	}
	return e;
}
signed main()
{
	scanf("%lld%lld",&m,&k);
	f[0]=0;g[0] = 0;
	f(i,0,k-1)f[i + 1] = (f[i] + (g[i] * qp(t,P - 2) % P + 1) * m) % P,g[i + 1] = (g[i] * qp(t,P-2)%P * (t + m -1) + m ) % P,t += m - 1; 
	cout<<f[k];
	return 0;
}