#include <bits/stdc++.h>
#define maxn 10000100
#define int long long
using namespace std;
const double eps = 1e-8;
const int mod = 1e9 + 9;
int f[maxn], inv[maxn];  //叶子节点的期望深度和

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

void solve() {
    int m, k, res = 0;
    cin >> m >> k;
    for (int i = 0; i < k; ++i)  inv[i] = qmi((m - 1) * i + 1, mod - 2, mod);
    for (int i = 1; i <= k; ++i) {
        // sum * (m - 1) * (i - 1) + (sum + (m - 1) * (i - 1) + 1) * m
        f[i] = (f[i - 1] * (m - 1) % mod * (i - 1) % mod + (f[i - 1] + (m - 1) * (i - 1) + 1) % mod * m % mod) % mod;
        f[i] = f[i] * inv[i - 1] % mod;

        // f[i] = ((m - 1) * (i - 1) % mod * f[i - 1] % mod + (f[i - 1] + 1) * m % mod) % mod;
        // f[i] = f[i] * qmi(1 + i * (m - 1), mod - 2, mod) % mod;
        res = (res + (f[i - 1] * inv[i - 1] % mod + 1) * m % mod) % mod;
    }
    cout << res << '\n';
}

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