#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lowbit(x) (x & (-x))
typedef long long ll;
typedef pair<int,int> pii;
mt19937 rnd(time(0));
const int N = 1e7 + 7;
const int mod = 1e9 + 9;
int a[N],b[N];
int qpow(int x,int n) {
    int res = 1;
    while(n) {
        if(n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}
void solve() {
    int m , k; cin >> m >> k;
    a[0] = 1;
    for(int i = 1;i < k;i++) {
        b[i - 1] = qpow(((m - 1) * (i - 1) + 1) % mod,mod - 2);
        (a[i] = ((m - 1) * i + 1) % mod * b[i - 1] % mod * a[i - 1] % mod + m) %= mod;
    }
    b[k - 1] = qpow(((m - 1) * (k - 1) + 1) % mod,mod - 2);
    int ans = 0;
    for(int i = 0;i < k;i++) (ans += a[i] * b[i]) %= mod;
    ans = ans * m % mod;
    cout << ans << "\n";
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    return 0;
}