#include <bits/stdc++.h>
#define int long long 
using namespace std;
typedef long long LL;
typedef std::pair<int, int> pii;
const int MX = 1e7 + 23;
const int MOD = 1e9 + 9;
 
int qpow(int a , int mod ){
    int b = mod - 2 , ans = 1 ; 
    while(b){
        if(b&1) ans = ans * a %  mod ; 
        a = a * a % mod ; 
        b /= 2 ; 
    }
    return ans ; 
}
 
int m, k;
LL f[MX];
LL inv[MX];
LL fac[MX];
signed main() {
    cin >> m >> k;// 
    f[0] = 0; 
    LL w = 1;
    fac[0] = 1;
    for (int i = 1; i <= k; ++i) {
        w = 1 + (m-1) * i ; 
        fac[i] = w;
    }
    for (int i = k; i >= 1; --i) {
       w = qpow(fac[i],MOD) ;
       inv[i] = w  ;   
    }
    int ans_t = 0 ; 
    for (int i = 1; i <= k; ++i) {
        f[i] = (( (m - 1) * (i - 1) % MOD  ) * f[i - 1] 
                +  (f[i - 1] + 1) * m) % MOD;
     
         f[i] = f[i] * inv[i] % MOD;
         ans_t = (ans_t+((f[i-1]+1)*m%MOD)) %MOD;  
    }
    
    cout << ans_t % MOD << endl;   
 
    return 0;
}