#include <bits/stdc++.h>
using namespace std;
const int P = 1e9+9;
using ll = long long;
#define M 10000006
int inv[M];
int Inv(ll x){
    if(x<M)return inv[x];
    else return 1ll*Inv(P%x)*(P-P/x)%P;
}
void Init(){
    inv[0]=inv[1]=1;
    for(int i=2;i<M;i++)
        inv[i]=1ll*inv[P%i]*(P-P/i)%P;
}
int m,K;
int f[M],g[M];
int main(){
    Init();
    cin>>m>>K;
    f[0]=1,g[0]=1;
    int x = 0;
    for(int i=1;i<=K;i++){
        ll x = 1ll*(m-1)*(i-1) + 1;
        int p = 1ll*f[i-1]*Inv(x)%P;
        f[i] = (f[i-1] + 1ll*m*(p+1) - p)%P;
        g[i] = (g[i-1] + 1ll*m*(p+1))%P;
    }
    cout<<(g[K] +P-(1ll*m*K%P+1)%P)%P<<endl;
    return 0;
}