#include<bits/stdc++.h>
#define int long long

const int mod = 1e9 + 9,N = 1e7 + 7;

int sum[N],dep[N],cnt[N],inv[N];

int QPOW(int a,int x)
{
    int ans = 1;
    while(x)
    {
        if(x & 1) ans = ans * a % mod;
        a = a * a % mod;x >>= 1;
    }
    return ans;
}



signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);std::cout.tie(0);

    int m,k;std::cin>>m>>k;
    sum[1] = m;dep[1] = 1;cnt[1] = m;
    for(int i = 2;i <= k;++i)cnt[i] = i * m - (i - 1);

    //inv[k] = QPOW(cnt[k],mod - 2);
    //for(int i = k - 1;i >= 1;--i)inv[i] = (inv[i + 1]  - m + 1 + mod) % mod;
    //std::cout<<inv[1]<<" "<<QPOW(cnt[1],mod-2)<<"\n";
    //std::cout<<inv[2]<<" "<<QPOW(cnt[2],mod-2)<<"\n";

    for(int i = 2;i <= k;++i)
    {
        sum[i] = (sum[i - 1] + m * (dep[i-1] + 1)) % mod;
        dep[i] = ((dep[i - 1] * (cnt[i - 1] - 1 + mod) % mod + (dep[i - 1] + 1) * m % mod) % mod * QPOW(cnt[i],mod-2)) % mod;
    }

    std::cout<<sum[k]<<"\n";

    return 0;
}