#include<bits/stdc++.h>
using namespace std;
const int P=1e9+9,M=1e7+1;
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=res*1ll*a%P;
        b>>=1;
        a=a*1ll*a%P;
    }
    return res;
}
int ni(int a){
    return ksm(a,P-2);
}
int m,k,cnt[M],ans;
int main(){
    scanf("%d%d",&m,&k);
    cnt[0]=1;
    for(int i=1;i<=k;i++)cnt[i]=cnt[i-1]+m-1;
    int sd=0;
    for(int i=1;i<=k;i++){
        ans=(ans+(sd+1)*1ll*m)%P;
        sd=(sd*1ll*(cnt[i-1]-1)+(sd+1)*1ll*m)%P*1ll*ni(cnt[i])%P;
    }
    printf("%d\n",ans);
}