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

typedef long long ll;
const int MOD = 1e9 + 9;
struct mint {
	int x;
	mint() : x(0) {}
	mint(int x) : x(x) {}
	mint operator+(int ot) const { return x + ot >= MOD ? x + ot - MOD : x + ot; }
	mint operator-(int ot) const { return x < ot ? x - ot + MOD : x - ot; }
	mint operator*(int ot) const { return 1ll * x * ot % MOD; }
	mint operator+=(int ot) { return *this = *this + ot; }
	mint operator-=(int ot) { return *this = *this - ot; }
	mint operator*=(int ot) { return *this = *this * ot; }
	operator int() { return x; }
};
mint mpow(mint a, ll x) {
	mint r = 1;
	while (x) {
		if (x & 1) r *= a;
		a *= a;
		x /= 2;
	}
	return r;
}

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);
	int m, k;
	cin >> m >> k;
	if (m == 1) {
		cout << (ll)k * (k + 1) / 2 % MOD << '\n';
		return 0;
	}
	mint a = 0, b = 0, c = 1;
	for (int i = 0; i < k; i++) {
		c *= (m - 1) * i + 1;
	}
	c = mpow(c, MOD - 2);
	a = 1 + mpow(m - 1, MOD - 2);
	b = mint(0) - mpow((m - 1) * (m - 1), MOD - 2) * m;
	a *= c;
	b *= c;

	for (int s = 1; s <= k; s++) {
		mint c = a * (k - s) * (m - 1) + a * m;
		mint d = b * (k - s) * (m - 1) + (a + b) * m;
		a = c; b = d;
	}
	b += mpow((m - 1) * (m - 1), MOD - 2) * m;
	cout << b << '\n';
}