#include <bits/stdc++.h>
using namespace std;

#define ll        long long
#define ull       unsigned long long
#define fir       first
#define sec       second
#define pii       pair<int, int>
#define pll       pair<long long, long long>
#define lowbit(a) (a & (-a))
#define SZ(a)     ((int)a.size())
#define all(a)    a.begin(), a.end()

constexpr int N = 2e7 + 50;
constexpr int INF = 0x3f3f3f3f;
constexpr ll LINF = 0x3f3f3f3f3f3f3f3f;
constexpr int mod = 1e9 + 9;
constexpr int dir[4][2] = {
    {-1,  0},
    { 0,  1},
    { 1,  0},
    { 0, -1},
};

mt19937_64 rnd(random_device{}());
uniform_int_distribution<ull> dist(0, ULLONG_MAX); // use dist(rnd)
const int M = 4e7 + 10; 

#define int long long


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

ll f[N], g[N];
void solve() {
//	int base = 600000038;
//	for(int i = 1; i <= 1000; ++i)
//		cout << i << ' ' << i * base % mod << '\n'; 
	
	int m, k; cin >> m >> k;
	g[0] = 1;
	for(int i = 1; i <= k; ++i) 
		g[i] = g[i - 1] + m - 1;
		
	f[0] = 0;
	for(int i = 1; i <= k; ++i)	
		f[i] = ((1ll * (m - 1) * f[i - 1] % mod) * qpow(g[i - 1], mod - 2) % mod + f[i - 1] + m) % mod; 
	ll Ans = 0;
	for(int i = 0; i < k; ++i)
		Ans = (Ans + f[i] * qpow(g[i], mod - 2)) % mod;
	Ans += f[k];
	Ans %= mod;
	cout << Ans << '\n';
}
/*
4 1 3 1
1 2 3 100
9 1 9 1
2 4 5
*/

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int _ = 1;
//    cin >> _;
    while (_--)
        solve();
    return 0;
}