#include <bits/stdc++.h>

using i64 = long long;

constexpr int P = 1e9 + 9;

i64 power(i64 a, i64 b)
{
	i64 res = 1;
	for( ; b; b >>= 1, a = a * a % P)
		if(b & 1) res = res * a % P;

	return res;
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int m, k; std::cin >> m >> k;

	i64 ans = 0, f = 0;
	for(int i = 1; i <= k; i++)
	{
		i64 inv = power(1LL * (i - 1) * (m - 1) + 1, P - 2);
		ans = (ans + f * inv % P + 1) % P;
		f = (f * (1LL * i * (m - 1) + 1) % P * inv % P + m) % P;
	}

	std::cout << ans * m % P << "\n";

	return 0;
}