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

#define F first
#define S second
#define ar array
#define ll long long
typedef int uci;
#define int long long

//adapted from:
//https://cp-algorithms.com/algebra/extended-euclid-algorithm.html
//https://cp-algorithms.com/algebra/module-inverse.html
long long migcdext(long long a, long long b, long long &c, long long &d){
	if(b == 0){
		c = 1;
		d = 0;
		return a;
	}
	long long t, t2;
	long long gcd = migcdext(b, a%b, t, t2);
	c = t2;
	d = t - (a/b)*t2;
	return gcd;
}

const int mod = 1e9 + 9;

long long modinv(long long a){
    const int m = mod;
	long long t, t2;
	long long gcd = migcdext(a, m, t, t2);
	if(gcd != 1){
		return -1;
	}else{
		long long res = (t%m + m)%m;
		return res;
	}
}


void solve(){
    int m, k; cin >> m >> k;

    int nodes = 1, leaves = 1;
    int nd = 0, ld = 0;

    for (int i = 0; i < k; i++) {
        long long add =  m * (ld + 1);
        ld = ((add + (leaves-1) * ld) % mod) * modinv(leaves + m-1) % mod;
        nd = (nd + add) % mod;

        leaves += m-1;
        nodes += m;
    }

    cout << nd << '\n';
}

uci main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    solve();
}