#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e7+10,M=1e9+9;
int f[N],ny[N],dp[N],zt[N];
int ksm(int a,int b,int c){
	int b1=b;
	zt[1]=a%c;
	int cnt=1;
	int ans=1;
	while(b1){
		cnt++;
		zt[cnt]=zt[cnt-1]*zt[cnt-1]%c;
		b1/=2;
	}
	cnt=0;
	while(b){
		cnt++;
		if(b&1){
			//cnt++;
			ans*=zt[cnt];
			ans%=c; 
		}
		b>>=1;
	}
	return ans;
}
signed main(){
	int m,k;
	cin>>m>>k;
	f[0]=1; 
	int maxx=1;
	for(int i=1;i<=k;i++){
		f[i]=f[i-1]-1+m;
		maxx=max(maxx,f[i]);
	}
	//for(int i=1;i<=k;i++)cout<<f[i]<<endl;
    if(maxx>10000000)maxx=10000000;
	dp[0]=0;
	ny[1]=1;
	for(int i=2;i<=maxx;i++){
		ny[i]=(M-M/i)*ny[M%i]%M;
	}
	for(int i=1;i<=k;i++){
		if(f[i]<=1e7){
			dp[i]=((dp[i-1]*f[i-1])%M*ny[f[i]]%M-(dp[i-1]*ny[f[i]]%M)+M)%M+m*dp[i-1]%M*ny[f[i]]%M+m*ny[f[i]]%M;
			dp[i]%=M;
		}else{
			int zqx=ksm(f[i],M-2,M);
			dp[i]=((dp[i-1]*f[i-1])%M*zqx%M-(dp[i-1]*zqx%M)+M)%M+m*dp[i-1]%M*zqx%M+m*zqx%M;
			dp[i]%=M;
		}
	}
	//for(int i=1;i<=k;i++)cout<<dp[i]<<endl;
	int ans1=dp[k]*f[k]%M;
	for(int i=1;i<k;i++){
		ans1=ans1+dp[i]%M;
		ans1%=M;
	}
	cout<<ans1<<endl;
	return 0;
}