#include <bits/stdc++.h>
using namespace std;
bool stB;
namespace SOL {

void debug(const char *msg, ...) {
#ifdef CLESIP
    va_list arg;
    static char pbString[512];
    va_start(arg,msg);
    vsprintf(pbString,msg,arg);
    cerr << "[DEBUG] " << pbString << "\n";
    va_end(arg);
#endif    
}

using i64 = long long;
using i128 = __int128_t;
template <typename T, typename L> bool chkmax(T &x, L y) { if (x < y) return x = y, true; return false; }
template <typename T, typename L> bool chkmin(T &x, L y) { if (y < x) return x = y, true; return false; }

const i64 P = 1e9 + 9;

i64 qpow(i64 a, i64 b) {
	i64 ret = 1;
	for (; b; b >>= 1) {
		if (b & 1)
			ret = ret * a % P;
		a = a * a % P;
	}
	return ret;
}

void ___solve() {
	i64 n, m; cin >> m >> n;

	i64 top = 0, sum = 0, bot = 1, av = 1;
	for (int i = 1; i <= n; i ++) {
		i64 cur = (sum + bot * av % P) % P * m % P;
		sum = (sum * av % P - sum + cur + P) % P;
		top = (top * av % P + cur) % P;
		bot = av * bot % P;
		av = av + m - 1;
	}
	// debug("top: %lld bot: %lld", top, bot);
	cout << top * qpow(bot, P - 2) % P << "\n";
}

}
bool edB;
signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	SOL::___solve();
#ifdef CLESIP
	// cerr << "Memory: " << (&stB - &edB) / 1024.0 / 1024.0 << "MB\n";
	// cerr << "Time: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
#endif
	return 0;
}