#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+9;
ll pw(ll x,ll y){
	if(y==0) return 1;
	if(y%2) return x*pw(x,y-1)%mod;
	ll res=pw(x,y/2);
	return res*res%mod;
}
ll f[10000001],inf[10000001];;
int main(){
	ios::sync_with_stdio(false);
	ll k,m;cin >> m >> k;
	ll el=0;
	ll ans=0;
	f[0]=1;
	for(int i=1; i<=k ;i++){
		f[i]=f[i-1]*(1+i*(m-1))%mod;
	}
	inf[k]=pw(f[k],mod-2);
	for(int i=k; i>=1 ;i--){
		inf[i-1]=inf[i]*(1+i*(m-1))%mod;
	}
	for(int i=0; i<k ;i++){
		ans=(ans+(el+1)*m)%mod;
		el=el*(1+(m-1)*i)+(m-1)*el+m;
		el%=mod;
		el=el*(f[i]*inf[i+1]%mod)%mod;
	}
	cout << ans << '\n';
}