#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lowbit(i) (i&-i)
#define rand() (myrand())
using namespace std;
mt19937 myrand(time(0));
const int mod = 1e9 + 9;
int n, m;
int qpow(int a, int x) {
	int res = 1;
	while(x) {
		if (x&1) res = 1ll*res*a%mod;
		a = 1ll*a*a%mod;
		x >>= 1;
	}
	return res;
}
int Add(int x, int y) {
	if (x + y > mod) return x + y - mod;
	if (x + y < 0) return x + y + mod;
	return x + y;
}
void solve() {
	cin >> m >> n;
	int s = 1, ans = 0, w = 0;
	for (int i = 1 ; i <= n ; ++i) {
		ans = Add(ans, 1ll*(w + 1)*m%mod);
		int ni = qpow(1ll*i*(m - 1)%mod + 1, mod - 2);
		w = Add(w, 1ll*m*ni%mod);
		s = 1ll*s*(1ll*i*(m - 1)%mod + 1)%mod;
	}
	cout << ans << '\n';
}
signed main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	return 0;
}