#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;

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

void solve(){ 
    
    cin >> n >> K;
    int A = 0; 
    int ans = 0;
    // for(int i = 0; i < K; i ++){
    //     int cnt = qmi((((n - 1LL) * (i)) + 1) % MOD, MOD - 2, MOD) % MOD;
    //     ans = (ans + (A * 1LL * cnt % MOD + 1) % MOD) % MOD;
    //     A = (A * ((n - 1LL) * (i + 1) % MOD + 1) % MOD * cnt % MOD + n) % MOD;;
    // }
    
    // cout << ans * 1LL * n % MOD << "\n";
    int fen = 0;

    int LP = 1, LS = 0, Edi = 1;

    for(int i = 1; i <= K;  i ++){ 
        ans = (ans + LS * 1LL * n + Edi * 1LL * n % MOD) % MOD;
        LS = ((LS * 1LL * (LP + n - 1) % MOD + n * 1LL * Edi % MOD)) % MOD;
        ans = ans * (LP - 1LL + n) % MOD;
        Edi = Edi * 1LL * (LP - 1 + n) % MOD;
        LP = (LP - 1 + n) % MOD;
        
    }
    cout << ans * 1LL * qmi(Edi, MOD - 2, MOD)  % 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;
}

/*

*/