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

const int M = 1e9 + 9;

int fp(int a,int b){
    int re=1;
    while(b){
        if(b&1)
            re = re * a % M;
        a = a * a % M;
        b = b >> 1;
    }
    return re;
}
int div(int n){
    return fp(n, M - 2);
}
void solve(){

    int m, k;
    cin >> m >> k;
    int pre = 1;
    int prev = 1;
    int e = 0;
    int ev = 0;
    for (int i = 1; i <= k;i++){ 
        ev += (e+1) * m%M;
        e = ((pre - 1) * e%M + m * (e + 1)%M) * (div(pre + m - 1))%M;

        ev %= M;
        pre += m - 1;
        prev += m;
        pre %= M;
        prev %= M;
    }
    cout << ev;
}

signed main(){
    int t=1;
//    cin>>t;
    while(t--)
        solve();
    return 0;
}