#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 9;

//a^k的快速幂
ll quick_power(ll a,ll k)
{
    ll res = 1;
    while(k){
        if(k&1)res = (res*a)%mod;
        a = (a%mod*a)%mod;
        k>>=1;
    }
    return res;
}
//a在模mod下的逆元,利用费马小定理求解，要求mod为素数
ll inv(ll a)
{
    return quick_power(a,mod - 2);
}

void solve()
{
    ll m,k;
    cin>>m>>k;
    vector<ll>f(k+10,0);
    ll d = 0;
    ll ans = 0;
    for(int i=1;i<=k;i++){
        ans = (ans + d) % mod;
        f[i] = (f[i-1] - d + m*(d+1)) % mod;
        d = (d + m*inv(i*m-(i-1))%mod) % mod;
        // cerr<<"d = "<<d<<"\n";
        // cerr<<f[i]<<"\n";
        
    }
    cout<<((ans + f[k])%mod + mod)%mod;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while(t--){
        solve();
    }
    return 0;
}