#include<bits/stdc++.h>
#define int long long
const int N=1e7+7;
const int p=1e9+9;
using namespace std;
int m,k;
int a[N],b[N],ip[N],inv[N];
int ksm(int a,int b){
	int res=1;
	for(;b;b>>=1){
		if(b&1) res=res*a%p;
		a=a*a%p;
	}
	return res;
}

signed main(){
	cin>>m>>k;
	
	a[0]=1; for(int i=1;i<=k;++i) a[i]=a[i-1]+m-1;
    b[0]=1; for(int i=1;i<=k;++i) b[i]=1LL*b[i-1]*a[i]%p;
    ip[k]=ksm(b[k],p-2);
    for (int i=k-1;i>=1;--i) ip[i]=1LL*ip[i+1]*a[i+1]%p;
    for (int i=1;i<=k;++i) inv[i]=1LL*ip[i]*b[i-1]%p;
    
	int E=0;
	int num=1;
	int ans=0;
	for(int i=1;i<=k;i++){
		int t=(E+1)*m%p;
		ans=(ans+t)%p;
		
		E=(E*(num-1)%p+t)%p*inv[i]%p;
		num+=m-1;
	}
	cout<<ans<<"\n";
}