#include <iostream>
#include <vector>

using namespace std;
using ll = long long;
const ll mod = 1e9+9;
ll modPow(ll n, ll p) {
	ll b = n, o = 1;
	while (p) {
		if (p&1) o = (b*o)%mod;
		p/=2;
		b = (b*b)%mod;
	}
	return o;
}

ll inv(ll n) {
	return modPow(n, mod-2);
}

int main() {
	ll m, k; cin >> m >> k;
	ll dleaf = 0, dnode = 0;
	ll leafCnt = 1;
	ll nodeCnt = 0;
	for (ll i = 0; i < k; i++) {
		ll aleaf = (dleaf * inv(leafCnt))%mod;
		dnode = dnode + aleaf;
		dnode %= mod;

		dleaf = dleaf + m*(aleaf+1) - aleaf + mod;
		dleaf %= mod;
		leafCnt += m-1;
		nodeCnt++;
	}
	cout << (dleaf + dnode)%mod << endl;
}