#include<bits/stdc++.h>
#define MAXN 1010
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define Rof(i,a,b) for (int i=(a);i>=(b);i--)
using namespace std;
#define maxn 10000007
#define mod 1000000009
#define ll long long

ll a[maxn];
ll mul[maxn];
ll inv[maxn];
ll E[maxn];
ll F[maxn];
ll M, K;

ll qpow(ll base, ll x)
{
    ll ans = 1;
    while(x) {
        if(x & 1) ans = ans * base % mod;
        base = base * base % mod, x >>= 1;
    }
    return ans;
}
int main(){
    std::ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> M >> K;
    mul[0] = 1;
    For(i, 1, K) a[i] = (1 + i * (M - 1)) % mod;
    For(i, 1, K) mul[i] = mul[i - 1] * a[i] % mod;
    ll iv = qpow(mul[K], mod - 2);
    Rof(i, K, 1) {
        inv[i] = iv * mul[i - 1] % mod;
        iv = iv * a[i] % mod;
    }
    // For(i, 1, K) cout << a[i] << " " << inv[i] << endl;
    For(i, 1, K) {
        F[i] = (F[i - 1] + (M - 1) * F[i - 1] % mod * inv[i - 1] % mod + M) % mod;
        E[i] = (E[i - 1] + (M) * F[i - 1] % mod * inv[i - 1] % mod + M) % mod;
    }
    // For(i, 1, K) cout << E[i] << endl;
    cout << E[K] << endl;
}
/*
6 2

2 6

83 613210 

*/