#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e7+10,M=1e9+9;
int ny[N],dp[N],zt[N],maxx,f[N];
int ksm(int a,int b,int c){
    int b1=b;
    zt[1]=a%c;
    int cnt=1;
    int ans=1;
    while(b1){
        cnt++;
        zt[cnt]=zt[cnt-1]*zt[cnt-1]%c;
        b1>>=1;
    }
    cnt=0;
    while(b){
        cnt++;
        if(b&1){
            //cnt++;
            ans*=zt[cnt];
            ans%=c; 
        }
        b>>=1;
    }
    return ans;
}
signed main(){
    int m,k;
    cin>>m>>k;
    f[0]=1; 
    for(int i=1;i<=k;i++){
        f[i]=f[i-1]-1+m;
    }
    dp[0]=0;
    ny[1]=1;
    for(int i=1;i<=k;i++){
        int zqx=ksm(f[i],M-2,M);
        dp[i] = (dp[i - 1] * (f[i - 1] - 1 + m) % M + m) * zqx;
        dp[i]%=M;
    }
    int ans1=dp[k]*f[k]%M;
    for(int i=1;i<k;i++){
        ans1+=dp[i];
        ans1%=M;
    }
    cout<<ans1<<endl;
    return 0;
}