#include<bits/stdc++.h>

using namespace std;

#define pll pair<ll, ll>
#define ll long long
const int mod = 1e9 + 9;
const int N = 1e7 + 50;

ll inv[N], a[N], p[N], ip[N];

ll fp(ll a, ll n)
{
    ll ans = 1;
    a %= mod;
    while (n)
    {
        if (n & 1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        n >>= 1;
    }
    return ans;
}

ll m, k;

void solve()
{
    cin >> m >> k;
    for (int i = 1; i <= k; i++) a[i] = (i * m - (i - 1)) % mod;
    p[0] = 1;
    for (int i = 1; i <= k; i++) p[i] = p[i - 1] * a[i] % mod;
    ip[k] = fp(p[k], mod - 2);
    for (int i = k - 1; i >= 1; i--)
    {
        ip[i] = ip[i + 1] * a[i + 1] % mod;
    }
    inv[1] = fp(m, mod - 2);
    for (int i = 2; i <= k; i++) inv[i] = ip[i] * p[i - 1] % mod;
    ll e = 0, ans = 0, num;
    for (int i = 1; i <= k; i++)
    {
        ans += (e + 1) * m;
        ans %= mod;
        if (i == 1) num = 1;
        else num = ((i - 1) * m - (i - 2)) % mod;
        e = ((e * (num - 1)) % mod + (e + 1) * m % mod) * inv[i] % mod;
    }
    cout << ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll T = 1;
    //cin >> T;
    while (T --)
    {
        solve();
    }
    
    return 0;
}