#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e7+10;
const int mod=1e9+9;
ll num[N],dp[N];

ll qpow(ll n,ll m)
{
	ll ans=1;
	while(m)
    {
		if(m&1) ans=ans*n%mod;
		m>>=1;
		n=n*n%mod;
	}
	return ans;
}

ll getInv(ll a)
{
	return qpow(a,mod-2);
}

int main()
{
    int m,k;
    ll ans=0;
    cin>>m>>k;
    num[0]=1;
    for(int i=1;i<=k;i++) num[i]=num[i-1]+m-1;

    dp[0]=0;
    for(int i=1;i<=k;i++)
    {
        dp[i]=((((dp[i-1]*num[i-1])%mod+((dp[i-1]+1)*m)%mod-dp[i-1])%mod)*getInv(num[i]))%mod;
        ans=(ans+dp[i-1])%mod;
    }
    // cout<<num[1]<<'\n';
    // cout<<(dp[1]*num[1])%mod<<'\n';
    ans=(ans+((dp[k]*num[k])%mod))%mod;
    cout<<ans;
    return 0;
}