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