#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e7+10,M=1e9+9;
int ny[N],dp[N],zt[N],maxx,f[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>>=1;
	}
	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; 
	for(int i=1;i<=k;i++){
		f[i]=f[i-1]-1+m;
		
	}
	//for(int i=1;i<=k;i++)cout<<f[i]<<endl;
//    if(f[k]>10000000)maxx=10000000;
//    else maxx=f[k];
	dp[0]=0;
	ny[1]=1;
//	for(int i=m;i<=f[k];i+=m-1){
//		cout<<i<<" "<<M%i<<" "<<ny[M%i]<<endl;
//		ny[i]=(M-M/i)*ny[M%i]%M;
//	}
	for(int i=1;i<=k;i++){
//		if(f[i]<=1e7){
//cout<<M%f[i]<<endl;
if(f[i]<=50000000){
	if(M%f[i]<=50000000&&ny[M%f[i]]){
			ny[f[i]]=(M-M/f[i])*ny[M%f[i]]%M;
			}else{
				ny[f[i]]=ksm(f[i],M-2,M);
			} 
			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;
	if(M%f[i]<=50000000&&ny[M%f[i]]){
			zqx=(M-M/f[i])*ny[M%f[i]]%M;
			}else{
				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;
}
            
			//cout<<i<<" "<<dp[i]<<endl;
//		}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;
}