#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 1000006;
const int MOD = 1e9 + 9;

inline int Mul(int x, int y) {
	return 1LL * x * y % MOD;
}

inline int Ksm(int x, int y) {
	int ret = 1;
	for (; y; y >>= 1) {
		if (y & 1) ret = Mul(ret, x);
		x = Mul(x, x);
	}
	return ret;
}

inline int Inv(int x) {
	return Ksm(x, MOD - 2);
}

int n, m, fac[MAXN], finv[MAXN];

void solve() {
	n = 1000000;
	fac[0] = 1;
	for (int i = 1; i <= n; ++i) {
		fac[i] = Mul(fac[i - 1], i);
	}
	finv[n] = Inv(fac[n]);
	for (int i = n; i >= 1; --i) {
		finv[i - 1] = Mul(finv[i], i);
	}
	scanf("%d %d", &n, &m);
	int ans = Mul(fac[n], finv[m]);
	int x = 1LL * n * (n - 1) / 2 % MOD;
	for (int i = 1; i <= m; ++i) {
		ans = Mul(ans, x);
		--x;
	}
	printf("%d\n", ans);
}

int main() {
	solve();
	return 0;
}