#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef long long LL ;
#define int LL
#define x first
#define y second
const int N = 1e3+10,mod = 1e9+9;
int qmi(int a,int k)
{
	int res= 1;
	while(k)
	{
		if(k&1) res=res*a%mod;
		a=a*a%mod;
		k>>=1;
	}
	return res;
}
int m,k;
void solve()
{
	cin>>m>>k;
	int ans = 0;
	int x= 0;
	int last = 1;
	for(int i= 1;i<=k;i++)
	{
		int cur = last + m-1;
		ans = (ans + m*(x+1)%mod)%mod;
		x=(x*(last-1)%mod +m*(x+1)%mod)%mod*qmi(cur,mod-2)%mod;
		last =cur;
	}
	cout<<ans<<"\n";
}
signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T = 1;
	//cin>>T;
	while(T--)
	{
		solve();
	}
}