#include<bits/stdc++.h>
using namespace std;
#define int long long
int m,k;
const int mod = 1e9+9 , maxn = 1e7+10;
int kasumi(int x,int y) {
	int ans=1,base=x;
	while (y) {
		if (y&1) ans=(ans*base)%mod;
		base=(base*base)%mod;
		y>>=1;
	}
	return ans;
}
int inv(int x) {
	return kasumi(x%mod,mod-2);
} 
int sum[maxn],qwq[maxn];
signed main(){
    ios::sync_with_stdio(false);
    //std::cin.tie(nullptr);std::cout.tie(nullptr);
    cin>>m>>k;
    sum[0]=0;
    for (int i=1;i<=k;++i) {
    	qwq[i]=inv((m-1)*(i-1)+1);
    	sum[i]=(sum[i-1]*(((m-1)*i+1)%mod)%mod*qwq[i]+m)%mod;
	}
	int ans=0;
	for (int i=1;i<=k;++i) {
		ans=(ans+(((((sum[i-1]*qwq[i])+1)%mod)*m)%mod))%mod;
	}
	cout<<ans%mod<<"\n";
	return 0;
}