#include<bits/stdc++.h>

using namespace std;
using ll = long long;

template<class T>
T qpow(T a, ll b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}

const int P = 1e9 + 9;

struct Mint{
    int x;

    Mint() : x(0){}
    Mint(int _x){
        if(_x < 0)_x += P;
        if(_x >= P)_x -= P;
        x = _x;
    }
    Mint(ll _x) {
        _x %= P;
        if(_x < 0)_x += P;
        x = _x;
    }
    int val() const {return x;}

    int norm(int a){
        if(a >= P) a -= P;
        if(a < 0)a += P;
        return a;
    }

    Mint inv() const{
        // assert(x != 0);
        return qpow(*this, P - 2);
    }

    Mint &operator+=(const Mint &a){
        x += a.x;
        if(x >= P)x -= P;
        return *this;
    }
    Mint &operator-=(const Mint &a){
        x -= a.x;
        if(x < 0)x += P;
        return *this;
    }
    Mint &operator*=(const Mint &a){x = 1ll * x * a.x % P; return *this;}
    Mint &operator/=(const Mint &a){return *this *= a.inv();}

    Mint &operator++(){x += 1; return *this;}
    Mint  operator++(int){Mint before(*this); x += 1; return before;}
    Mint &operator--(){x -= 1; return *this;}
    Mint  operator--(int){Mint before(*this); x -= 1; return before;}

    friend Mint operator+(const Mint &a, const Mint &b){
        Mint res = a;
        res += b;
        return res;
    }
    friend Mint operator-(const Mint &a, const Mint &b){
        Mint res = a;
        res -= b;
        return res;
    }
    friend Mint operator*(const Mint &a, const Mint &b){
        Mint res = a;
        res *= b;
        return res;
    }
    friend Mint operator/(const Mint &a, const Mint &b){
        Mint res = a;
        res /= b;
        return res;
    }

    Mint operator+() { return *this; }
    Mint operator-() { return Mint(0) -= *this; }

    friend bool operator==(const Mint &a, const Mint &b) { return a.x == b.x; }
    friend bool operator!=(const Mint &a, const Mint &b) { return a.x != b.x; }
    friend bool operator< (const Mint &a, const Mint &b) { return a.x < b.x; }
    friend bool operator<=(const Mint &a, const Mint &b) { return a.x <= b.x; }
    friend bool operator> (const Mint &a, const Mint &b) { return a.x > b.x; }
    friend bool operator>=(const Mint &a, const Mint &b) { return a.x >= b.x; }

    friend istream &operator>>(istream &is, Mint &a){
        ll b;
        cin >> b;
        a = Mint(b);
        return is;
    }
    friend ostream &operator<<(ostream &os, const Mint &a){
        return os << a.val();
    }

};


const int N = 2e5 + 5;
vector<Mint> fac, inv;

void init(){
    fac.resize(N);
    inv.resize(N);
    fac[0] = 1;
    for(int i = 1; i < N; ++i)fac[i] = i * fac[i - 1];
    inv[N - 1] = fac[N - 1].inv();
    for(int i = N - 1; i > 0; --i){
        inv[i - 1] = i * inv[i];
    }
}

void solve(){
    int m, k;
    cin >> m >> k;
    vector<Mint> pre(k + 1);
    pre[0] = 1;
    for (int i = 1; i <= k; ++i) {
        pre[i] = pre[i - 1] * (1 + i * (m - 1));
    }
    vector<Mint> inv_pre(k + 1);
    inv_pre[k] = pre[k].inv();
    for (int i = k; i > 0; --i) {
        inv_pre[i - 1] = inv_pre[i] * (1 + i * (m - 1));
    }
    Mint ans, E;
    for (int i = 0; i < k; ++i) {
        ans += (E + 1) * m;
        E = (i * (m - 1) * E + (E + 1) * m) * inv_pre[i + 1] * pre[i];
    }
    cout << ans << "\n";
}

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    init();
    int t = 1;
    // cin >> t;
    for (int i = 0; i < t; ++i) {
        solve();
    }
    return 0;
}