///by Saton.
#include<bits/stdc++.h>
#define PI acos(-1)
#define fi first
#define se second 
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
#define LL long long
#define ll __int128
#define DD double double
#define LD long double
#define rep(i,a,b) for(int i = (a);i <= (b);i ++)
#define lep(i,a,b) for(int i = (a);i >= (b);i --)
#define FLUSH fflush(stdout)
using namespace std;
const int N = 1e7 + 10,mod =  1e9+9,P = 131;
LL n,m,k;
 
LL qmi(LL a,LL b,LL p) {LL res = 1;while(b) {if(b&1) res = (LL)res*a%p;a = (LL)a*a%p;b >>= 1;}return res%p;}

LL f[N];
void solve() {
    cin >> m >> k;
    f[0] = 1;
    LL ans = 0;
    rep(i,1,k) {
        ans = (ans + f[i-1]*m%mod) % mod;
        LL inv = qmi(i*(m-1)+1,mod-2,mod);
        f[i] = (f[i-1] + m*inv%mod) % mod; 
    }
    
    cout << ans;
} 

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
       
    return 0;
}  
/*   /\_/\
*   (= ._.)
*   / >  \>
*/