#include <bits/stdc++.h>
using namespace std;
#define maxn 10000005
#define int long long
#define ll long long
const int p=1e9+9;
int lstl,lstans,lstcnt;

int qpow(int a,int b){
    int ans=1,tmp=a;
    while(b){
        if(b&1){
            ans=1LL*ans*tmp%p;
        }
        tmp=1LL*tmp*tmp%p;
        b>>=1;
    }
    return ans;
}

void solve(){
    int m,k;cin>>m>>k;
    lstl=0,lstans=0,lstcnt=1;
    
    for(int i=1;i<=k;i++){
        int a1=0,a2=0;
        a1=(1LL*(lstl+1)*m+1LL*(lstcnt-1)*lstl)%p*qpow(lstcnt+m-1,p-2)%p;
        a2=((lstans+1LL*(lstl+1)*m))%p;
        lstcnt=lstcnt+m-1;
        if(lstcnt>=p)lstcnt-=p;
        lstl=a1,lstans=a2;
        //cout<<"i="<<i<<' '<<lstl<<' '<<lstans<<' '<<lstcnt<<'\n';
        
    }
    cout<<lstans;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int TT=1;//cin>>TT;
    while(TT--){
        solve();
    }
}