#include <bits/stdc++.h>
#define long long long int
#define DEBUG
using namespace std;

// @author: pashka

int mod = 1000000009;

struct mint {
    int value = 0;

    constexpr mint() : value() {}

    mint(const long &x) {
        value = normalize(x);
    }

    static long normalize(const long &x) {
        long v = x % mod;
        if (v < 0) v += mod;
        return v;
    }

    bool operator==(const mint &x) { return value == x.value; };

    mint operator+(const mint &x) { return value + x.value; };

    mint operator-(const mint &x) { return value - x.value; };

    mint operator*(const mint &x) { return (long) value * x.value; };

    void operator+=(const mint &x) { value = normalize(value + x.value); };

    void operator-=(const mint &x) { value = normalize(value - x.value); };
};

mint power(mint a, long b) {
    mint res = 1;
    while (b > 0) {
        if (b & 1) {
            res = res * a;
        }
        a = a * a;
        b >>= 1;
    }
    return res;
}

mint inv(mint a) {
    return power(a, mod - 2);
}

int main() {
    ios::sync_with_stdio(false);

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

    mint s = 0;
    mint sr = 0;
    mint c = 1;
    mint p = 1;
    for (int i = 0; i < k; i++) {
//        mint e = s * inv(c);
//        sr += (e + 1) * m;
//        s = s - e + (e + 1) * m;
//        c = c + m - 1;

        p = p * c;
        sr = sr * c + (s + p) * m;
        s = s * c - s + (s + p) * m;

        c = c + m - 1;

//        cout << (s * inv(p)).value << "\n";
//        cout << (sr * inv(p)).value << "\n";
    }
    sr = sr * inv(p);
    cout << sr.value << "\n";

    return 0;
}