#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 n, int p) {
    int ans = 1;
    while(n) {
        if(n & 1) {
            ans = ans % p * a % p;
        }
        a = a % p * a % p;
        n >>= 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])%M*zqx%M-(dp[i-1]*zqx%M)+M)%M+m*dp[i-1]%M*zqx%M+m*zqx%M;
        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;
}