#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair

void fileio()
{
  #ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  #endif
}
void termin()
{
  #ifdef LGS
  std::cout<<"\n\nEXECUTION TERMINATED";
  #endif
  exit(0);
}

using namespace std;

const LL MOD=1e9+9;

LL qpow(LL x,LL a)
{
	LL res=x,ret=1;
	while(a>0)
	{
		if(a&1) (ret*=res)%=MOD;
		a>>=1;
		(res*=res)%=MOD;
	}
	return ret;
}

LL m,k;

int main()
{
  fileio();

  cin>>m>>k;
  LL ans=0,lsum=0,lc=1;
  rep(i,k)
  {
    LL rlc=qpow(lc,MOD-2),v=(m*lsum%MOD*rlc+m)%MOD;
    (ans+=v)%=MOD;
    (lsum+=MOD+v-lsum*rlc%MOD)%=MOD;
    lc+=m-1;
  }
  cout<<ans<<endl;

  termin();
}