#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

const int MOD = 1e9 + 9;

int add(int a, int b) {
    return a + b >= MOD ? a + b - MOD : a + b;
}

int sub(int a, int b) {
    return a >= b ? a - b : a + MOD - b;
}

int mul(int a, int b) {
    return (1ll * a * b) % MOD;
}

int pw(int x, int n) {
    int res = 1;
    while (n) {
        if (n % 2 == 0) {
            x = mul(x, x);
            n /= 2;
        } else {
            res = mul(res, x);
            --n;
        }
    }
    return res;
}

const int MAXK = 1e7 + 5;
int fact[MAXK], invf[MAXK];


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int m, k;
    cin >> m >> k;

    fact[0] = 1;
    for (int i = 1; i < MAXK; ++i) {
        fact[i] = mul(fact[i - 1], 1 + (m - 1) * i);
    }
    invf[MAXK - 1] = pw(fact[MAXK - 1], MOD - 2);
    for (int i = MAXK - 1; i > 0; --i) {
        invf[i - 1] = mul(invf[i], 1 + (m - 1) * i);
    }
    int ans = k;
    for (int i = 1; i < k; ++i) {
        ans = add(ans, mul(m, mul(k - i, mul(invf[i], fact[i - 1]))));
    }
    cout << mul(ans, m) << "\n";

    
    return 0;
}