#include<bits/stdc++.h>
#define ll long long
#define N 10000010
using namespace std;
int m,k;
ll mod=1e9+9,f[N],sum;

inline ll ksm(ll p,ll k){
	ll rt=1;
	while(k){
		if(k&1) rt=rt*p%mod;
		p=p*p%mod;
		k>>=1;
	}
	return rt;
}

int main(){
	cin>>m>>k;
	for(int i=1;i<=k;i++){
		f[i]=((i-1)*(m-1)*f[i-1]+m*(f[i-1]+1))%mod*ksm(i*(m-1)+1,mod-2)%mod;
		sum+=(f[i-1]+1)*m;
		sum%=mod;
	}
	cout<<sum;
	return 0;
}