#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
const int P=1000000009;

int a[10000005];

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;
}

int main() {
    ll m,k;
    cin>>m>>k;
    a[0]=0;
    ll ans=1;
    for(int i=1;i<k;i++){
        ll x1=quickpow(((m-1)*(i-1)+1),P-2);
        ll x2=quickpow(((m-1)*i+1),P-2);
        a[i]=((((a[i-1]*((m-1)*i+1))%P)*x1)%P+m)%P;
        ans=(ans+1+(a[i]*x2)%P)%P;
    }
    ans=ans*m%P;
    cout<<ans;
    return 0;
}
/*
2
6
2 1 2 2 1 1
4
1 2 1 1
*/