#include <bits/stdc++.h>

#define x first
#define y second
#define min(a, b) ((a) < (b)?(a):(b))
#define max(a, b) ((a) > (b)?(a):(b))

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL, LL> PLL; 
using PIII = pair<int, PII>;
using i128 = __int128;
using ULL = unsigned long long;

const int N = 10000100, M = 60010, MOD = 1e9 + 9, Base = 13331;
const int inf = 2e9, xf3 = 0x3f3f3f3f;
const LL INF = 4e18, XF3 = 0x3f3f3f3f3f3f3f3f;


LL n;
int K;
string s;
LL fact[N], infact[N];

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

void init(int nn){
    fact[0] = infact[0] = 1;

    for(int i = 1; i <= nn; i ++){
        infact[i] = qmi((((n - 1) * (i)) + 1) % MOD, MOD - 2, MOD);
    }    
}

void solve(){ 
    
    cin >> n >> K;
    init(K);
    LL A = 0; 
    LL ans = 0;
    for(int i = 0; i < K; i ++){
        ans = (ans + (A * infact[i] % MOD + 1) % MOD) % MOD;
        A = A * ((n - 1LL) * (i + 1) % MOD + 1) % MOD * infact[i] % MOD + n;
        A = A % MOD;
    }
    cout << ans * n % MOD << "\n";
    
    return;
}

int main(){
	
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0); 
	
	//cout<<fixed<<setprecision(0)<<"\n";
    int _ = 1;  
	// cin>>_;
	
	while(_ --){
		solve();
	} 
	
	return 0;
}

/*

*/