#include<bits/stdc++.h>
#define int long long int
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int maxn=1e6+5;
const int inf=1e18;
int tt=1;
int m,k;
const int mod=1e9+9;
int quick(int x,int y)
{
    int yy=1;
    while(y)
    {
        if(y&1)
            yy=yy*x%mod;
        y>>=1;
        x=x*x%mod;
    }
    return yy;
}
void solve()
{
    cin>>m>>k;
    int cnt=1,ex=0;
    int sum=0;
    for(int i=1;i<=k;i++)
    {
        sum=(ex+sum)%mod;
        ex=((cnt-1+mod)%mod*ex%mod + m*(ex+1)%mod)%mod *quick((cnt-1+m)%mod,mod-2)%mod;
        cnt=(cnt+m-1)%mod;
    }
    cout<<(ex*cnt%mod+sum)%mod<<'\n';
 }
signed main()
{
	ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout<<fixed<<setprecision(10);
//    cin>>tt;
    for(int i=1;i<=tt;i++)
    solve();
}