#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll p=1e9+9;
ll ksm(ll a,ll b){
    if(b==0){
        return 1;
    }
    ll ans=ksm(a,b/2);
    ans=ans*ans%p;
    if(b&1){
        ans=ans*a%p;
    }
    return ans;
}
ll inv(ll x){
    return ksm(x,p-2);
}
int main(){
    ll m,k;
    cin>>m>>k;
    vector<ll> val(k+1);
    val[0]=1;
    for(int i=1;i<=k;i++){
        val[i]=(val[i-1]+m-1)%p;
    }
    vector<ll> f(k+1),g(k+1);
    f[0]=1;
    for(int i=1;i<=k;i++){
        f[i]=(f[i-1]*(val[i-1]-1)%p+m*(f[i-1]+1)%p)%p;
        f[i]=f[i]*inv(val[i])%p;
        g[i]=(g[i-1]+m*f[i-1]%p)%p;
    }
    cout<<g[k]<<endl;
    return 0;
}