#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+9;
const int N=1e7+5;
int m,k;
int Pow(int a,long long k)
{
    int ans=1;
    while(k)
    {
        if(k&1)ans=1ll*ans*a%mod;
        a=1ll*a*a%mod;
        k>>=1;
    }
    return ans;
}
int fct[N],inv[N];
int INV(int x){return inv[x]*1ll*fct[x-1]%mod;}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>m>>k;
    int ans=0,lst=0;
    fct[0]=1;
    for(int i=1;i<=k;i++)fct[i]=1ll*fct[i-1]*((m-1)*i+1)%mod;
    inv[k]=Pow(fct[k],mod-2);
    for(int i=k-1;i>=0;i--)inv[i]=1ll*inv[i+1]*((m-1)*(i+1)+1)%mod;
    for(int i=1;i<=k;i++)
    {
        ans+=(lst+1)*1ll*m%mod;
        ans%=mod;
        lst=(lst*1ll*((m-1)*(i-1))%mod+(lst+1)*1ll*m%mod)%mod;
        lst=lst*1ll*INV(i)%mod;
    }   
    cout<<ans<<'\n';
}