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