#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];
int main() {
    scanf ("%d%d", &m, &k);
    f[1] = 1, ans = m;
    for (int i = 1; i < k; i++) {
        f[i + 1] = (f[i] + m * fpow(1 + 1ll * (m - 1) * i, mod - 2)) % mod;
        ans = (ans + f[i + 1] * m) % mod;
    }
    printf ("%lld\n", ans);
    return 0;
}