/*
sum(x)表示对x集合求和
len(x)表示对x集合求数量
设T[i]表示操作i次后的树
B[i]表示i次操作后的叶节点集合
D[i]表示i次操作后的一个叶节点期望深度

则有D[i] = (sum (B[i - 1])) / (len (B[i - 1])) + 1

len(B[i - 1]) = (i - 1) * (k - 1) + 1

ans = M * sum (D[1] + ... + D[k])

sum (B[i]) = sum (B[i - 1]) - D[i] + M (D[i] + 1)

最终式子为E (sum (B[i])) = ((M - 1) * i + 1) / ((M - 1) * (i - 1) + 1) * E (sum (B[i - 1])) + M

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

using namespace std;

const int mod = 1E9 + 9;

inline int read () {
    int w = 1, s = 0; char ch = getchar ();
    for (; ! isdigit (ch); ch = getchar ()) if (ch == '-') w = -1;
    for (; isdigit (ch); ch = getchar ()) s = (s << 1) + (s << 3) + (ch ^ 48);
    return s * w;
}

int power (int x, int p) {
    int sum = 1;
    for (; p; p >>= 1) {
        if (p & 1) sum = sum * x % mod;
        x = x * x % mod;
    }
    return sum;
}

int inv (int x) {
    x %= mod;
    return power (x, mod - 2);
}

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

    vector <int> f (k + 1);
    vector <int> g (k + 1);

    g[0] = 1;
    for (int i = 1; i <= k; i ++) {
        g[i] = g[i - 1] * ((m - 1) * i + 1) % mod;
    }
    f[k] = inv (g[k]);
    for (int i = k - 1; i >= 0; i --) {
        f[i] = f[i + 1] * ((m - 1) * (i + 1) + 1) % mod;
    }
    for (int i = k; i >= 1; i --) {
        f[i] = f[i] * g[i - 1] % mod;
    }

    vector <int> A (k + 1);
    for (int i = 1; i <= k; i ++) {
        A[i] = (((m - 1) * i + 1) % mod * f[i - 1] % mod * A[i - 1] + m) % mod;
    }

    int ans = 0;
    for (int i = 0; i < k; i ++) {
        ans += m * (A[i] * f[i] % mod + 1);
        ans %= mod; 
    }

    cout << ans << '\n';
} 

signed main () {
	ios::sync_with_stdio (false);
    cin.tie (nullptr);
    
	int T = 1; 
	// cin >> T;
	// T = read ();

	while (T --) {
		solve ();
	}
	
	return 0;
}