#include<bits/stdc++.h>

typedef long long int ll;
typedef unsigned long long int ull;
#define pii pair<int,int>
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"
#define pb push_back
#define lowbit(x) ((x) & (-x))

using namespace std;
const int INF = 0x3f3f3f3f;
const double EPS=1e-10;
const double Pi=3.1415926535897;
const int mod=1e9+9;
const int maxn=1e5+5;

ll m, k;
ll e;
ll ans;

ll ksm(ll a, ll n){
	ll res=1;
	a%=mod;
	while(n){
		if(n&1) res=res%mod*a%mod;
		a=a%mod*a%mod;
		n>>=1;
	}
	return res;
}

ll inv(ll a){
	return ksm(a, mod-2);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	
	cin>>m>>k;
	e=0, ans=0;

	for(int i=1;i<=k;i++){
		ans=(ans+m*(e*inv((m-1)*(i-1)+1)%mod+1)%mod)%mod;
		e=((m-1)*i+1)%mod*inv((m-1)*(i-1)+1)%mod*e+m;
		e%=mod;
	}
	cout<<ans<<"\n";

	return 0;
}

/*

*/