#include <bits/stdc++.h>
#define int long long
#define endl '\n' 
#define buff ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
int m,k;
const int mod = 1e9 + 9;
int quickpow(int x,int y){
    int res = 1;
    while(y){
        if(y&1) res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}
signed main(){
    cin>>m>>k;
    int ans = 0,e = 0,num = 1;
    for(int i=1;i<=k;i++){
        ans=(ans+m*(e+1))%mod;
        int n=(num-1+m)%mod;
        e=(e*(num-1)+m*(e+1)%mod)%mod*quickpow(n,mod-2)%mod;
        num=n;
    }
    cout<<ans<<endl;
    return 0;
}