// Code by Heratino & Nelofus
// Narcissus & どうか安寧な記憶を

#include <bits/stdc++.h>
using i64 = long long;

//{{{誰にもなれない 私 胸張ってさ
template<typename Ta, typename Tb>
inline void chkmax(Ta &a, const Tb &b) {if (a < b)	a = b;}
template<typename Ta, typename Tb>
inline void chkmin(Ta &a, const Tb &b) {if (a > b)	a = b;}
char buf[1 << 20], *P1, *P2;
inline char gc() {
	if (P1 == P2)
		P2 = (P1 = buf) + fread(buf, 1, 1 << 20, stdin);
	return P1 == P2 ? EOF : *P1++;
}
template<typename T>
inline void read(T &ans) {
	ans = 0;
	T w = 1;
	char c = gc();
	while (!isdigit(c)) {
		if (c == '-')	w = -1;
		c = gc();
	}
	while (isdigit(c)) {
		ans = (ans << 3) + (ans << 1) + (c ^ 48);
		c = gc();
	}
	ans *= w;
}
template<typename T, typename ...Ts>
void read(T &a, Ts&... other) {
	read(a);
	read(other...);
}
//}}}

constexpr int mod = 1e9 + 9;
constexpr int N = 1e7 + 10;
inline int Plus(const int &x, const int &y) {return x + y >= mod ? x + y - mod : x + y;}
inline int Minu(const int &x, const int &y) {return x - y < 0 ? x - y + mod : x - y;}
inline int f_pow(int x, int k) {
	int base = 1;
	for (; k; k >>= 1, x = 1ll * x * x % mod)
		if (k & 1)
			base = 1ll * base * x % mod;
	return base;
}

int m, k;
int ifac[N];
int fac[N];
int ED[N];
int pinvf[N], pinvq[N];

inline int inv(int x) {
	return x ? 1ll * ifac[x] * fac[x - 1] % mod : 1;
}

int main() {
#ifdef HeratinoNelofus
	freopen("input.txt", "r", stdin);
#endif

	fac[0] = 1;
	for (int i = 1; i < N; i++)
		fac[i] = 1ll * fac[i - 1] * i % mod;
	ifac[N - 1] = f_pow(fac[N - 1], mod - 2);
	for (int i = N - 2; i >= 0; i--)
		ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;

	read(m, k);

	auto invpinv = [&](const int &x) -> int {
		return Plus(1ll * (x - 1) * (m - 1) % mod, 1);
	};
	pinvf[0] = 1;
	for (int i = 1; i <= k; i++)
		pinvf[i] = 1ll * pinvf[i - 1] * invpinv(i) % mod;
	pinvq[k] = f_pow(pinvf[k], mod - 2);
	for (int i = k - 1; i >= 0; i--)
		pinvq[i] = 1ll * pinvq[i + 1] * invpinv(i + 1) % mod;

	ED[0] = 0;
	int ans = 0;
	for (int i = 1; i <= k; i++) {
		int pinv = 1ll * pinvq[i] * pinvf[i - 1] % mod;
		ans = Plus(ans, Plus(1ll * ED[i - 1] * pinv % mod, 1));
		ED[i] = 1ll * ED[i - 1] * (Plus(1ll * i * (m - 1) % mod, 1)) % mod * pinv % mod;
		ED[i] = Plus(ED[i], m);
	}
	std::cout << 1ll * m * ans % mod << '\n';
	return 0;
}