#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int mod = 1e9 + 9;

ll qpow(ll a, ll b) {
	ll res = 1;
	while(b) {
		if(b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	ll M, K;
	cin >> M >> K;

	ll last = 0, cur = 0, ans = 0;
	for(int i = 1; i <= K; i ++ ) {
		cur = (1ll * i * (M - 1) + 1) % mod * qpow((1ll * (i - 1) * (M - 1) + 1) % mod, mod - 2) % mod * last % mod;
		cur = (cur + M) % mod;

		ans = (ans + (last * qpow((1ll * (i - 1) * (M - 1) + 1) % mod, mod - 2) % mod + 1) % mod) % mod;
		last = cur;
	}

	cout << ans * M % mod << '\n';

	return 0;
}