#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 power(int a, int b, int mod = M) {
    int res = 1;
    for (; b; b /= 2, a *= a, a %= M) {
        if (b % 2) {
            res *= a;
            res %= M;
        }
    }
    return res;
}
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=power(f[i],M-2);
        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;
}