#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int mod = 1e9 + 9;
int quickpow(int x,int y){
	int res = 1;
	while(y){
		if(y&1) res = res * x % mod;
		x = x * x %mod;
		y>>=1;
	}
	return res;
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int m,k;
	cin>>m>>k;
	int ans = 0;
	int n = 1,all = 0;
	for(int i=1;i<=k;i++){
		int e = all*quickpow(n,mod-2)%mod;
		ans = (ans + m*(e+1)%mod)%mod;
		int p = quickpow(n,mod-2);
		
		int temp = (n*all%mod+(m-1)*all%mod+n*m%mod) %mod;
		all = p * temp % mod;
		n=n-1+m;
	}
	cout<<ans<<endl;
	return 0;
	
}