#include <iostream>

using namespace std;

const int mod = 1e9 + 9;
#define ll long long

long long power(long long a, int n) {
    ll ans = 1;
    while(n)
    {
        if(n&1) ans = ans * a % mod;
        a = a*a%mod;
        n >>= 1;
    }
    return ans;
}
long long modInverse(long long a) {
    return power(a, mod - 2);
}


int main() {
    int n, k;
    cin >> n >> k;
    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));
        v %= mod;
        sum = sum - 1 + n;
        sum %= mod;
        // cout << ans << endl;
    }
    
    cout << ans << endl;

    return 0;
}