#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define mkp make_pair
#define pb push_back
typedef pair <int, int> pii;

inline int read() {
    int x = 0, f = 0;
    char c = getchar();
    while (!isdigit(c)) {if (c == '-') f = 1; c = getchar();}
    while (isdigit(c)) x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f? -x : x;
}

const int Mod = 1e9 + 9;
inline int fastpow(int x, int p) {
    int ans = 1;
    while (p) {
        if (p & 1) ans = ans * x % Mod;
        x = x * x % Mod;
        p >>= 1;
    }
    return ans;
}

signed main() {
    int m, K, ans = 0;
    cin >> m >> K;
    int c = 1, d = 0;
    for (int i = 1; i <= K; ++i) {
        ans = (ans + (d + 1) * m) % Mod;
        d = (c * d + m * (d + 1) - d) % Mod * fastpow(c + m - 1, Mod - 2) % Mod;
        c += (m - 1);
    }
    cout << ans << endl;
    return 0;
}