#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); i ++)
#define int long long
using namespace std;

const int M = 1e7 + 5, MOD = 1e9 + 9;
int f[M], s[M];

int qmi(int a, int b){
	int res = 1;
	while(b){
		if(b & 1) res = res * a % MOD;
		a = a * a % MOD;
		b >>= 1; 
	}
	return res;
}
void sol(){
	int m, k;
	cin >> m >> k;
	if(k == 1){
		cout << m << "\n";
		return ;
	}
	int n = 1;
	f[1] = 1;
	rep(i, 2, k){
		n = (n + m - 1) % MOD;
		f[i] = (f[i - 1] + m * qmi((n + m - 1) % MOD, MOD - 2) % MOD) % MOD;
	}
	rep(i, 1, k){
		s[i] = (s[i - 1] + (f[i] + 1) * m % MOD) % MOD;
	}
	cout << (s[k - 1] + m) % MOD << "\n";
	return ;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int T = 1;
//	cin >> T;
	while(T --){
		sol();
	}
	return 0;
}