#include <bits/stdc++.h>
#define pii pair<long long,long long>
#define mp make_pair
using namespace std;
typedef long long ll;

template<typename T>inline void read(T &x) {
	x = 0;
	int f = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-')
			f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = x * 10 + c - '0';
		c = getchar();
	}
	x *= f;
}

template<typename T>inline void write(T x) {
	if (x < 0) {
		putchar('-');
		x = -x;
	}
	if (x > 9) {
		write(x / 10);
	}
	putchar(x % 10 + '0');
}
const int mod = 1e9 + 9;
ll leaf = 1, leafd = 0, total = 0;
int s = 0;

ll fpow(int x, int y) {
	int res = 1;
	for (; y; y >>= 1, x = 1ll * x * x % mod)
		if (y & 1)
			res = 1ll * res * x % mod;
	return res;
}

int main() {
	int m = 100, k = 1e7;
	cin >> m >> k;
	for (int i = 1; i <= k; i++) {
		total = (total + (leafd + 1) * m) % mod;
		leafd = (leafd * (leaf - 1)) + (leafd + 1) * m;
		leafd %= mod;
		leaf += m - 1;
		leafd = leafd * fpow(leaf, mod - 2) % mod;
	}
	cout << total;
	return 0;
}