#include<bits/stdc++.h>
#define int long long
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
using pii = pair<int, int>;
using db = double;
void init();
void solve();

signed main(){
	fast init();
	int t = 1;
//	cin >> t;
	while(t--){
		solve();
	}
}

const int N = 1e7 + 10, M = N * 2, P = 998244353,mod=1000000009;

void init(){
	return;
}

int qpow(int x,int ind)
{
	int ans(1),now(x);
	while(ind)
	{
		if(ind&1)
		{
			ans*=now;
			ans%=mod;
		}
		now*=now;
		now%=mod;
		ind>>=1;
	}
	return ans;
}
int m,f,K,g,h[N];

void solve(){
	cin>>m>>K;
	h[0]=1;
	for(int i=1;i<=K;i++)h[i]=h[i-1]*((i-1)*(m-1)+1)%mod;
	for(int i=1;i<=K;i++)g=(m*f+g*((i-1)*(m-1)+1)+m*h[i])%mod,f=((m-1)*f+f*((i-1)*(m-1)+1)+m*h[i])%mod;
	cout<<g*qpow(h[K],mod-2)%mod;
}