#include <bits/stdc++.h>
#define int long long
#define endl "\n"
const int mod = 1e9 + 9;
const int N = 1e5 + 50;
using namespace std;
int quickpow(int n, int m){
	int res = 1;
	while(m){
		if(m & 1){
			res = res * n % mod;
		}
		n = n * n % mod;
		m = m >> 1;
	}
	return res;
} 
void slove(){
	int m, k; cin >> m >> k;
	int s1 = m, s2 = m, s3 = m;
	for(int i = 2; i <= k; i++){
		int p = quickpow(s1, mod - 2);
		int ss1 = s1 + m - 1;
		int ss2 = s2 + (m - 1) * s2 % mod * p % mod + m;
		int ss3 = s3 + m + m * s2 % mod * p % mod;
		s1 = ss1 % mod;
		s2 = ss2 % mod;
		s3 = ss3 % mod; 
	}
	cout << s3 << endl;
}
signed main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T = 1;
	//cin >> T;
	while(T--){
		slove();
	}
	return 0;
}