#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
typedef long long LL;

template<class T>
T qmi(T a,LL k){
    T res = 1;
    while(k){
        if(k & 1)res *= a;
        a *= a;
        k >>= 1;
    }
    return res;
}

struct MInt{
    int v;
    const static int Mod;
    MInt() : v() {}
    MInt(LL _v) : v(norm(_v % Mod)) {}
    static int getMod(){
        return Mod;
    }
    int norm(int x) const {
        if(x < 0){
            x += Mod;
        }else if(x >= Mod){
            x -= Mod;
        }
        return x;
    }
    int val() const {return v;}
    MInt operator-() const {
        MInt res;
        res.v = norm(Mod - v);
        return res;
    }
    MInt inv() const {
        return qmi(*this,Mod - 2);
    }
    MInt &operator*=(MInt rhs) & {
        v = 1LL * v * rhs.v % Mod;
        return *this;
    }
    MInt &operator+=(MInt rhs) & {
        v = norm(v + rhs.v);
        return *this;
    }
    MInt &operator-=(MInt rhs) & {
        v = norm(v - rhs.v);
        return *this;
    }
    MInt &operator/=(MInt rhs) & {
        return *this *= rhs.inv();
    }
    friend MInt operator*(MInt lhs, MInt rhs) {
        return 1LL * lhs.val() * rhs.val();
    }
    friend MInt operator+(MInt lhs, MInt rhs) {
        return lhs.val() + rhs.val();
    }
    friend MInt operator-(MInt lhs, MInt rhs) {
        return lhs.val() - rhs.val();
    }
    friend MInt operator/(MInt lhs, MInt rhs) {
        return 1LL * lhs.val() * rhs.inv().val();
    }
    friend std::istream &operator>>(std::istream &is, MInt &a) {
        LL v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const MInt &a) {
        return os << a.val();
    }
    friend bool operator<(MInt lhs,MInt rhs) {
        return lhs.val() < rhs.val();
    }
    friend bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
};
const int MInt::Mod = 1e9 + 9;
using Z = MInt;

void solve(){
    int m,k;
    cin >> m >> k;
    vector<Z> dp(k + 1);
    vector<Z> pre(k + 1),suf(k + 1);
    vector<Z> inv(k + 1);

    for(int i = 0;i <= k;i++)pre[i] = suf[i] = 1LL + i * (m - 1);
    for(int i = 1;i <= k;i++)pre[i] *= pre[i - 1];
    for(int i = k - 1;i >= 1;i--)suf[i] *= suf[i + 1];
    Z tmp = pre[k].inv();
    inv[0] = 1;
    inv[k] = tmp * pre[k - 1];
    for(int i = 1;i <= k - 1;i++)inv[i] = tmp * pre[i - 1] * suf[i + 1];

    Z res = 0;
    for(int i = 1;i <= k;i++){
        res += dp[i - 1];
        dp[i] = dp[i - 1] + Z(m) * inv[i];
    }
    res += dp[k] * (1 + k * (m - 1));
    cout << res << endl; 

}   

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }

    return 0;
}