#include <bits/stdc++.h>
using LL = long long;
// #define int LL
#define lc u << 1
#define rc u << 1 | 1
#define endl '\n'
#define aLL(v) v.begin(), v.end()
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 5, mod = 1e9 + 9;
LL qpow(LL x, LL k)
{
    LL tem = 1;
    while (k)
    {
        if (k & 1)
            tem = (tem * x) % mod;
        x = (x * x) % mod;
        k >>= 1;
    }
    return tem;
};
void solve()
{
    LL m, k;
    cin >> m >> k;
    vector f(k + 1, 0ll), dp(k + 1, 0ll);
    dp[0] = 0;
    f[0] = 1;
    LL ans = 0;
    for (int i = 1; i <= k; i++)
    {
        f[i] = (f[i - 1] + m - 1) % mod;
        ans += (dp[i - 1] + 1) * m % mod;
        ans %= mod;
        LL tem = (dp[i - 1] * (f[i - 1] - 1) % mod + (dp[i - 1] + 1) * m % mod) % mod;
        // cout << tem << endl;
        dp[i] = tem * qpow(f[i], mod - 2) % mod;
    }

    cout << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    // int ttt;
    // cin >> ttt;
    // while (ttt--)
    solve();
    return 0;
}