#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e7+10,M=1e9+9;
int dp[N],maxx,f[N];
int qpow(int a, int n, int p = M) {
    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;
    for(int i=1;i<=k;i++){
        int zqx=qpow(f[i],M-2);
        dp[i]=(dp[i-1]*f[i-1])%M*zqx%M-dp[i-1]*zqx%M+m*dp[i-1]%M*zqx%M+m*zqx%M;
        dp[i]%=M;
        dp[i] += M;
        dp[i] %= M;
    }
    int ans1=dp[k]*f[k];
    ans1 %= M;
    for(int i=1;i<k;i++){
        ans1+=dp[i];
        ans1%=M;
    }
    cout<<ans1<<endl;
    return 0;
}