#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("O2")
using namespace std;
#define int long long
#define ll long long
#define llu unsigned long long
#define endl "\n"

typedef pair<int, int> PII;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const long long inf = 1LL << 60;
const int mod = 1e9 + 9;
const int N = 1e7 + 10;
//f[i][j] 表示第i次操作深度为j的点的期望个数

int ksm(int a, int b) 
{
    a = a % mod; 
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int inv(int x) 
{
    return ksm(x, mod - 2);
}

void solve()
{
    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 * inv((sum + n - 1));
        v %= mod;
        sum = sum - 1 + n;
        sum %= mod;
    }
    
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(20);
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}