#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int mod=1e9+9;
const int maxk=1e7+10;

int qpow(int a,int b=mod-2){
	int res=1;
	while(b){
		if(b&1)
			res=(ll)res*a%mod;
		a=(ll)a*a%mod;
		b>>=1;
	}
	return res;
}

int s[maxk],sv[maxk],inv[maxk],a[maxk];

int E=0;
int main(){
    int m,k,Kl=1,El=0;
    cin>>m>>k;
    
    a[0]=1;
    for(int i=1;i<=k;i++)
    	a[i]=a[i-1]+m-1;
    s[0]=1;
	for(int i=1;i<=k;i++)
		s[i]=(ll)s[i-1]*a[i]%mod;
	sv[k]=qpow(s[k]);
	for(int i=k;i;i--)
		sv[i-1]=(ll)sv[i]*a[i]%mod;
	for(int i=1;i<=k;i++)
		inv[i]=(ll)sv[i]*s[i-1]%mod;
    
    int i=1;
    while(k--){
        E=(E+(ll)(El+1)*m)%mod;
        El=((ll)El*(a[i-1]-1)+(ll)m*(El+1))%mod*inv[i]%mod;
        i++;
    }
    cout<<E<<endl;
	return 0;
}