#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+9;
int fast(int x,int k)
{
	int ret=1;
	while(k)
	{
		if(k&1) ret=ret*x%mod;
		x=x*x%mod;
		k>>=1;
	}
	return ret;
}
void solve()
{
	int m,k;
	cin>>m>>k;
	int ret=0;
	int ans=0;
	for(int i=1;i<=k;++i)
	{
		int tmp=ret*((m-1)*(i-1)%mod)%mod+(ret+1)*m%mod;
		ans+=(ret+1)*m%mod;

		tmp=tmp%mod;
		tmp=tmp*fast((m-1)*i%mod+1,mod-2)%mod;
		ret=tmp%mod;
		
		ans%=mod;
	}
	cout<<ans%mod<<'\n';

}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T=1;
	//cin>>T;
	while(T--) solve();
	return 0;
}