#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const ll maxn = 1e7 + 10;
const ll maxm = 1e7 + 10;
const ll inf = 0x3f3f3f3f;
const ll P = 1e9 + 9;
ll quickpow(ll x, ll y) {
    ll ans = 1;
    while (y) {
        if (y & 1) ans *= x;
        ans %= P;
        y >>= 1;
        x *= x;
        x %= P;
    }
    return ans % P;
}

ll A[maxn], B[maxn];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll m, k;
    cin >> m >> k;
    A[0] = 0;
    B[0] = 0;
    // cout << quickpow(3, 5);
    for (ll i = 1; i <= k; i++) {
        ll ni = quickpow((m - 1) * (i - 1) + 1, P - 2);
        A[i] = (A[i - 1] * ((m - 1) * ni % P + 1) % P + m % P) % P;
        B[i] = (B[i - 1] + A[i - 1] * ni % P) % P;
    }
    cout << (A[k] + B[k]) % P;
    return 0;
}