#include<bits/stdc++.h>
#define N 100005
#define re 
#define ll long long
#define P 1000000009
using namespace std;
int n,m,K,q,T;
inline void Rd(int &res){
	re char c;res=0;
	while(c=getchar(),c<48);
	do res=(res<<3)+(res<<1)+(c^48);
	while(c=getchar(),c>47);
}
inline int Pow(int x,int k){
	int res=1;
	while(k){
		if(k&1)res=1ll*res*x%P;
		x=1ll*x*x%P;
		k>>=1;
	}
	return res;
}
int main(){
	Rd(m),Rd(K);
	int a=0,b=0,c=1;
	int sum=0;
	for(int i=1;i<=K;i++){
		int d=b+1;
		d=1ll*d*m%P;
		a=(a+d)%P;

		sum=(0ll+sum-b+d+P)%P;
	
		c=(c+m-1)%P;

		b=1ll*sum*Pow(c,P-2)%P;
	}

	printf("%d\n",a);

	return 0;
}