#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 m = 1, k = 10000000; 
	cin >> m >> k;
	g[0] = 1;
	for(int i = 1; i <= k; ++i) 
	{
		g[i] = g[i - 1] + m - 1;
		g[i] = 1ll * g[i] * g[i - 1] % mod;
	}
	g[k] = qpow(g[k], mod - 2);
	for(int i = k; i >= 1; --i)
	{
		g[i - 1] = 1ll * g[i - 1] * g[i] % mod;
	}
	int pv = qpow(m - 1, mod - 2);
	for(int i = 1; i <= k; ++i)
	{
		g[i] = inv[i]  * pv % 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) * g[i - 1] % mod + f[i - 1] + m) % mod; 
//		pre = qpow(g[i], mod - 2);
		if(i < k) Ans = (Ans + f[i] * g[i]) % 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;
}