#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define endl '\n'
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef tuple<int,LL,LL> TPL;
typedef pair<LL,LL> PII;
const int N=1e7+7,inf=0x3f3f3f3f;const LL Linf=0x3f3f3f3f3f3f3f3fLL;
LL qsm(LL a,LL b,LL p){LL res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;}
LL lowbit(LL x){return x&-x;}
const LL mod=1e9+9;
LL M,K;
LL res,dep[N],cnt[N],a[N];
LL up[N],down[N];
void init(){
    LL tt=1;
    up[0]=down[0]=1;
    for(int i=1;i<=K;i++){
        tt+=M-1;
        up[i]=up[i-1]*tt%mod;
    }
    down[K] = qsm(up[K],mod-2,mod);
	for (int i = K-1; i; i--){
        down[i] = down[i + 1] * tt % mod;
        tt -= M - 1;
    }
}
void solve(){
    cin>>M>>K;
    init();
    dep[0]=0,res=0,cnt[0]=1;
    for(int i=1;i<=K;i++){
        res=(res+(dep[i-1]+1)*M%mod)%mod;
        dep[i]=(dep[i-1]*(cnt[i-1]-1)%mod+(dep[i-1]+1)*M%mod)*up[i-1]%mod*down[i]%mod;
        cnt[i]=(cnt[i-1]+M-1);
    }
    cout<<res<<endl;
}
int main(){
   IOS
   int T=1;
   //cin>>T;
    while(T--)solve();

    return 0;
}