#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e7 + 5, mod = 1e9 + 9;
inline long long fpow (long long a, long long b) {
    long long res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res % mod;
}
int m, k;
long long ans, f[N], fac[N], inv[N];
int main() {
    scanf ("%d%d", &m, &k);
    f[1] = 1, ans = m;
    fac[0] = 1;
    for (int i = 1; i <= k; i++) fac[i] = (1 + (m - 1) * i) * fac[i - 1] % mod;
    inv[k] = fpow(fac[k], mod - 2);
    for (int i = k; i >= 1; i--) inv[i - 1] = (1 + (m - 1) * i) * inv[i] % mod;
    for (int i = 1; i < k; i++) {
        f[i + 1] = (f[i] + m * inv[i] % mod * fac[i - 1]) % mod;
        ans = (ans + f[i + 1] * m) % mod;
    }
    printf ("%lld\n", ans);
    return 0;
}