#include<bits/stdc++.h>

using namespace std;
using LL = long long;
using ll = long long;
const int N = 10000005;
#define rep(i,a ,b )  for(int i = a ;i<=b;i++)
#define pre(i,a ,b )  for(int i = a ;i>=b;i--)
#define pb push_back
#define sc(x) scanf("%d",&x)
ll dp[N];
ll f[N];
ll dp2[N];
const int mod=1e9+9;
ll ksm(ll a,ll b){ll res=1;
while(b){
	if(b%2==1)res=res*a%mod;a=a*a%mod;b/=2;
}
return res;
}
ll ny[N];
void solve() {
	int m,k;
	sc(m);sc(k);
	f[0]=1;
	rep(i,1,k)f[i]=(f[i-1]+m-1)%mod;
	/*rep(i,2,k){
		ny[i]=(mod-mod/i)*ny[mod%i]%mod;
	}*/
	ll res=0;
	rep(i,1,k){
		ll tmp=ksm(f[i-1],mod-2);
		dp[i]=dp[i-1]+(dp[i-1]*(m-1)%mod+f[i-1]*m%mod)*tmp%mod;//dp[i]为叶子节点深度之和 
		dp[i]%=mod;
		res=(res+(dp[i-1]*m%mod+f[i-1]*m%mod)*tmp)%mod;
	//	cout<<dp[i-1]*m%mod+f[i-1]*m%mod*ksm(f[i-1],mod-2)%mod<<" "<<endl;
	}
	cout<<res<<endl; 
}


int main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    //cin >> t ;

    while (t--) {
        solve();
    }

    return 0;


}