#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for (int i=(x);i<=(y);++i)
#define per(i,x,y) for (int i=(x);i>=(y);--i)
const int P = 1e9+9;
const int N = 305;
typedef long long ll;
ll qmi(ll x, ll y) {
	ll res = 1;
	while (y) {
		if (y & 1) res = res * x % P;
		x = x*x % P;
		y >>= 1;
	}
	return res;
}
void solve() {
	ll m, k;
	cin >> m >> k;
	ll ans = 1;
	ll a = 1;
	ll b = 1;
	rep(i, 1, k) {
		ll d = a * qmi(b, P - 2) % P;
		b = b + m - 1;
		a = ((a - d + P) % P + (m * (d + 1) % P));
		ans = (ans + ((d + 1) * m % P)) % P;
	}
	ans = (ans + P - ((k*m + 1) % P)) % P;
	cout << ans ;
	return;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
//	cin >> t;
	while (t--)
		solve();
	return 0;
}
/*
6 3
a?b??c
2 2 2
1 1 1
1 0 2
*/