#include <bits/stdc++.h>

using namespace std;
using LL = long long;
using PII = pair<LL , int> ;
using ULL = unsigned long long;

const int N = 1e7 + 10,Mod = 1e9 + 9;

LL a[N] , b[N];

LL qmi(LL a , LL b){
    LL res = 1;
    while(b){
        if(b & 1) res = res * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return res;
}

void solved() {
    LL m , k;
    cin >> m >> k;

    LL ans = 0;
    for(int i = 1 ; i <= k ; i ++ ){

        LL inv = qmi((m - 1) * (i - 1) + 1 , Mod - 2);

        LL res = ((m - 1) * i + 1) % Mod * inv % Mod;
        a[i] = (res * a[i - 1]) % Mod;
        a[i] = (a[i] + m) % Mod;

        res = a[i - 1] * inv % Mod;
        b[i] = (b[i - 1] + res) % Mod;

        ans = (ans + b[i]) % Mod;
    }
    cout << (b[k] + a[k]) % Mod << "\n";
}

int main(){

//      freopen("D:\\dev\\code\\sunwking\\1.in" , "r" , stdin);

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
//    cin >> t;

    while(t -- )
        solved();


    return 0;
}