#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using ull = unsigned long long;
constexpr int N = 1e7 + 10;
constexpr int inf = 1e9 + 10;
constexpr ll llinf = 1e18 + 10;
constexpr int mod = 1e9 + 9;
void debug() {
    std::cerr << "\n";
}
template<typename T, typename... Args>
void debug(T val, const Args&... args) {
    std::cerr << val << " ";
    debug(args...);
}
template<typename T>
void debug(const std::vector<T>& vec) {
    for (const T& x : vec) std::cerr << x << ' ';std::cerr << "\n";
}
template <typename T>
T power(T a, int b) {
    T ans = 1;
    while (b) {
        if (b & 1) ans *= a;
        a *= a;
        b >>= 1;
    }
    return ans;
}
template <int M>
struct modint {
    modint() : x(0) {}
    template <typename T> modint(T n) { n %= M; if (n < 0) n += M; this->x = n; }

    modint& operator+=(const modint& r) { x += r.x; if (x >= M) x -= M; return *this; }
    modint& operator-=(const modint& r) { x -= r.x; if (x < 0) x += M; return *this; }
    modint& operator*=(const modint& r) { x = (int)((long long)x * r.x % M); return *this; }
    modint inv(long long k = M - 2) const { return power(*this, k); }
    modint& operator/=(const modint& r) { return *this *= r.inv(); }

    modint& operator--() { if (--x == -1) x = M - 1; return *this; }
    modint& operator++() { if (++x == M) x = 0; return *this; }
    modint operator--(int) { modint t = *this; --*this; return t; }
    modint operator++(int) { modint t = *this; ++*this; return t; }

    modint operator-() const { return 0 - *this; }
    modint operator+() const { return *this; }
    constexpr int mod() const { return M; }

    friend modint operator+(modint l, const modint& r) { return l += r; }
    friend modint operator-(modint l, const modint& r) { return l -= r; }
    friend modint operator*(modint l, const modint& r) { return l *= r; }
    friend modint operator/(modint l, const modint& r) { return l /= r; }

    friend bool operator==(const modint& l, const modint& r) { return l.x == r.x; }
    friend bool operator!=(const modint& l, const modint& r) { return l.x != r.x; }
    friend std::istream& operator>>(std::istream& in, modint& r) { return in >> r.x; }
    friend std::ostream& operator<<(std::ostream& out, const modint& r) { return out << r.x; }

    int x;
};
using mint = modint<mod>;
mint f[N];
void ncl3() {
    int n, m;
    std::cin >> m >> n;
    way[0] = 1;
    for (ll i = 0; i < n; i++) {
        f[i + 1] = f[i] + (m * f[i] - f[i] + i * m + (i * m + 1 - i) * m) * mint(i * m + 1 - i).inv();
    }
    std::cout << f[n] << "\n";
}
/*
    预处理、找性质缩小范围、集合思想、正难则反、穷举
*/
int main() {
#ifdef LOCAL
    clock_t time = clock();
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
#endif
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t = 1;
    // std::cin >> t;
    while (t--) {
        ncl3();
    }
#ifdef LOCAL
    std::cout << "Time Used:" << clock() - time << "ms" << "\n";
#endif
    return 0;
}

answer.code: In function ‘void ncl3()’:
answer.code:68:5: error: ‘way’ was not declared in this scope
   68 |     way[0] = 1;
      |     ^~~