#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << " == " << x << endl
#define el '\n'
typedef long long ll;
const ll mod = 1000000009;
const ll inf = 2147483647;
const int N = 1e7 + 10;
ll fac[N], ifac[N];
ll qpow(ll a, ll b)
{
	ll ret = 1;
	while (b) {
		if (b & 1)
			ret = ret * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ret;
}
void init()
{
	fac[0] = 1;
	for (int i = 1; i < N; i++)
		fac[i] = fac[i - 1] * i % mod;
	ifac[N - 1] = qpow(fac[N - 1], mod - 2);
	for (int i = N - 1; i; i--) {
		ifac[i - 1] = ifac[i] * i % mod;
	}
}
ll up(ll x)
{
	return (x % mod + mod) % mod;
}
ll inv(ll x)
{
	return qpow(x, mod - 2);
}
void solve()
{
	int m, k;
	cin >> m >> k;
	ll e = 0, lase = 0, ans = 0, lasans = 0;
	ll tot = 1;
	for (int i = 1; i <= k; i++) {
		lasans = ans;
		ans = lasans + m * (e + 1);
		ans = up(ans);
		lase = e;
		e = up(lase * tot - lase + (lase + 1) * m);
		tot += m - 1;
		e = up(e);
		e = e * inv(tot);
		e = up(e);
		// cout << i << " " << ans << endl;
	}
	cout << ans << endl;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T = 1;
	// cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}