#include<bits/stdc++.h>
#define ll long long

using namespace std;

const int mod = 1e9 + 9, N = 1e7 + 10;

ll qmi(ll a, ll k)
{
    ll res = 1;
    while (k)
    {
        if (k & 1)res = res * a % mod;
        a = a * a % mod;
        k >>= 1;
    }
    return res;
}


void solve()
{
    ll f = 0, g = 0, cnt = 1;
    ll m, k; cin >> m >> k;
    for (int i = 1; i <= k; i++) {
        f = (f + m * (g + 1)) % mod;
        g = (g * (cnt - 1) + m * (g + 1)) % mod * qmi(cnt + m - 1, mod - 2) % mod;
        cnt = (cnt + m - 1) % mod;
    }
    cout << f;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    while (t--)solve();
    return 0;
}