#include<bits/stdc++.h>
using namespace std ;
#define int long long
const int MAXN = 1e7 + 10 ;
const int mod = 1e9 + 9 ;
int dp[MAXN], inv[MAXN], ans ;
inline int quick_pow (int a, int b) {
	int res = 1 ;
	while (b) {
		if (b & 1) {
			res *= a ;
			res %= mod ;
		}
		a *= a ;
		a %= mod ;
		b >>= 1 ;
	}
	return res ;
}
signed main () {
	int m, k ;
	cin >> m >> k ;
	for (int i = 1 ; i <= k ; i++) {
		inv[i] = quick_pow (((m - 1) * (i - 1) % mod + 1) % mod , mod - 2) ;
		dp[i] = (dp[i - 1] % mod) + (m - 1) * (dp[i - 1] * inv[i] % mod) + m ;
		dp[i] %= mod ; 
	}
	for (int i = 1 ; i <= k ; i++) {
		ans += m * (dp[i - 1] * inv[i] % mod) + m ;
		ans %= mod ;
	}
	cout << ans ;
}