#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128_t int128;
typedef pair<int, int> pii;
#define iofast    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define lowbit(x) (x & (-x))
#define inv(x)    qpow(x, mod - 2)
#define debug(x)  cout << (#x) << " = " << x << endl
#define range(x)  (x).begin(), (x).end()

const int iINF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1000000009;

/*---------------------------------------*/
inline int add(int a, int b, const int mod = mod)
{
    return (a += b) >= mod ? a - mod : a;
}
inline int sub(int a, int b, const int mod = mod)
{
    return (a -= b) < 0 ? a + mod : a;
}
inline int mul(int a, int b, const int mod = mod)
{
    return 1ll * a * b % mod;
}
int qpow(int a, int b)
{
    int ans = 1;
    for (; b; b >>= 1) {
        if (b & 1)
            ans = mul(ans, a);
        a = mul(a, a);
    }
    return ans;
}
void solve()
{
    int m, k;
    cin >> m >> k;

    int f = 0;
    int tag = mul(m, m);
    int ans = 0;
    for (int i = 1; i <= k; ++i) {
        ans = add(ans, f);
        ans = add(ans, m);
        f = add(f, mul(tag, qpow(add(1, mul(i, (m - 1))), mod - 2)));
    }

    cout << ans << '\n';
}

/*---------------------------------------*/

int main()
{
    iofast;
    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}