#include <bits/stdc++.h>
using namespace std;

#define int long long 
#define endl '\n'
const int N = 100010, mod = 1e9 + 9;
int a[N];


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


void solve()
{
    int m,k;cin >> m >> k;
    int t = 0;
    int now = 1, tmp = 1;
    int res = 0;
    int las = 0;
    for(int i = 0;i < k ;i++)
    {
        int las = qs((m - 1) * (i)%mod + 1, mod - 2);
        res += (t * las + 1);
        t = ((m  - 1) * (i + 1) + 1) % mod * las %mod * t % mod + m;
        res %= mod;
    }
    res = (res + mod) % mod;
    cout << res * m % mod << endl;

}


signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    
    solve();
}