#include<bits/stdc++.h>
#ifdef LOCAL
#include "Essentials/algo/debug.h"
#else
#define debug(...)    69
#define debugArr(...)  69
#endif
using namespace std;

typedef long long     ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>   pll;

const int N = 5e5 + 23;
const ll inf = 1e18;

#define F           first
#define S           second
#define pb          push_back
#define kill(x)     cout<<x<<endl, exit(0);
#define all(x)      x.begin(),x.end()
#define sz(x)       (int)x.size()
#define lc          (v << 1)
#define rc          ((v<<1) |1)

const int mod = 1e9+9;
ll pw(ll a , ll b , ll md = mod) {
	ll ans = 1;
	while(b) {
		if(b&1)
			ans = ans * a % md;
		
		b >>= 1;
		a = a * a % md;
	}
	return ans;
}

const int K = 1e7+2;
int fac[K];
int inv[K];
int dp[K], ways[K];
int m , k;

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
	
	fac[0] = 1;
	for(int i = 1 ; i < K ; i ++)
		fac[i] = 1ll * fac[i-1] * i % mod;
	
	inv[K-1] = pw(fac[K-1] , mod-2);
	for(int i = K-1 ; i ; i --)
		inv[i-1] = 1ll * inv[i] * i % mod;
	
	cin >> m >> k;
	ways[1] = 1;
	for(int i=2; i<K; i++) ways[i] = (1+ll(i-1)*(m-1))%mod;
	
	for(int i=k-1; i>=1; i--) ways[i] = 1ll*ways[i]*ways[i+1]%mod;
	
	dp[1] = 1;
	ll sum = 1+1;
	ll cur = 1;
	for(int i = 2 ; i <= k ; i ++) {
		dp[i] = 1ll * m * sum % mod * fac[i-2] % mod;
		sum = 1ll * sum * (m-1) % mod;
		cur = cur * (1 + 1ll*(i-1)*(m-1)%mod) % mod;
		sum = (sum + 1ll * (dp[i] + cur) * inv[i-1] % mod) % mod;
	}
	ll ans = 0;
	for(int i = 1 ; i <= k ; i ++)
		(ans += 1ll * dp[i] * (i==k ? 1 : ways[i+1])%mod * m % mod) %= mod;
	cout << 1ll*ans*pw(ways[1], mod-2)%mod << endl;
	
 	return 0;
}







// Jumpsuit, Jumpsuit cover me!
// Jumpsuit, Jumpsuit cover me!