#pragma GCC optimize(2)
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll mod=1e9+9;
ll a[10000001];
ll pre[10000001];
ll sv[10000001];
ll inv[10000001];
ll fastpow(ll base,ll po){
	ll ans=1;
	while(po){
		if(po&1){
			ans=ans*base%mod;
		}
		base=base*base%mod;
		po>>=1;
	}
	return ans;
}
void solve(){
	ll m,k;
	cin>>m>>k;
	pre[0]=1;
	for(int i=1;i<=k;i++){
		a[i]=i*(m-1)+1;
		pre[i]=pre[i-1]*a[i]%mod;
	}
	sv[k]=fastpow(pre[k],mod-2);
	for(int i=k-1;i>=0;i--){
		sv[i]=sv[i+1]*a[i+1]%mod;
	}
	for(int i=1;i<=k;i++){
		inv[i]=sv[i]*pre[i-1]%mod;
	}
	ll ans=m*k;
	ll temp=0;
	for(int i=1;i<=k-1;i++){
		temp+=inv[i]*(k-i)%mod;
		temp%=mod;
	}
	temp=temp*m%mod*m%mod;
	ans=(ans+temp)%mod;
	cout<<ans;
}
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}