#include <iostream>

using namespace std;


long long power(long long base, int exp, int mod) {
    if (base == 0) {
        return 0;
    }
    if (exp == 1) {
        return base;
    }
    if ((exp & 1) == 1) {
        return (power((base * base) % mod, (exp >> 1), mod) * base) % mod;
    } else {
        return power((base * base) % mod, (exp >> 1), mod);
    }
}
long long modInverse(long long a, int mod) {
    long long power(long long base, int exp, int mod);
    return power(a, mod - 2, mod);
}


int main() {
    int n, k;
    cin >> n >> k;
    int mod = 1e9 + 9;
    long long ans = 0;
    long long v = 0;
    long long sum = 1;

    for (int i = 1; i <= k; i++) {
        ans += (v + 1) * n;
        ans %= mod;
        v = ((v + 1) * n + (sum - 1) * v) % mod * modInverse((sum + n - 1) % mod, mod);
        v %= mod;
        sum = sum - 1 + n;
        sum %= mod;
        // cout << ans << endl;
    }
    
    cout << ans << endl;

    return 0;
}