#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];
ll inv[N];
void solve() {
//	int base = 600000038;
//	for(int i = 1; i <= 1000; ++i)
//		cout << i << ' ' << i * base % mod << '\n'; 
	
	int m = 1, k = 10000000; 
	cin >> m >> k;
	g[0] = 1;
	for(int i = 1; i <= k; ++i) 
		g[i] = g[i - 1] + m - 1;
	inv[1] = 1;
	for(int i = 2; i <= 10000000; ++i)
    {
        inv[i] = (1ll * inv[mod % i] * (-mod / i) % mod + mod) % mod;
    }
//	for(int i = 1; i <= k; ++i)
//	{
//		if(mod % g[i] >= 10000000) 
//		{
//			cout << "!!!\n";
//			return ;
//		}
//		g[i] = (1ll * inv[mod % g[i]] * (-mod / g[i]) % mod + mod) % mod;
//		
//	}
	ll Ans = 0;	
	f[0] = 0;
	ll pre = 1;
	for(int i = 1; i <= k; ++i)	
	{
		
		f[i] = ((1ll * (m - 1) * f[i - 1] % mod) * pre % mod + f[i - 1] + m) % mod; 
		pre = qpow(g[i], mod - 2);
		if(i < k) Ans = (Ans + f[i] * pre) % 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;
}