#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++) {
		dnode = nodeCnt*dnode + dleaf;
		dnode %= mod;
		dnode *= inv(nodeCnt+1);
		dnode %= mod;

		dleaf = (leafCnt+m-1)*dleaf + m;
		dleaf %= mod;

		leafCnt += m-1;
		nodeCnt++;

		dleaf *= inv(leafCnt);
		dleaf %= mod;
	}
	ll out = dleaf*leafCnt + dnode * nodeCnt;
	out %= mod;
	cout << out << endl;
}