#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e7 + 2;
int f[N], dp[N];
const int mod = 1e9 + 9;
int qsm(int x, int y)
{
    int res = 1;
    while (y)
    {
        if (y & 1)
            res = res * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return res;
}
void solve()
{
    int m, k;
    cin >> m >> k;
    f[0] = 1;
    dp[0] = 0;
    int ans = 0;
    for (int i = 1; i <= k; ++i)
    {
        f[i] = (f[i - 1] - 1 + m) % mod;
        dp[i] = (dp[i - 1] * (f[i - 1] - 1 + m) % mod + m) % mod * qsm(f[i], mod - 2) % mod;
        ans += dp[i - 1];
        ans %= mod;
    }
    ans += dp[k] * f[k] % mod;
    ans %= mod;
    cout << ans << "\n";
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // int t;
    // cin>>t;
    // while(t--)
    solve();
    return 0;
}