#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#include <map>
#include <vector>
#include <unordered_map>
#include <set>
#include <cmath>
#include <unordered_set>
#include <iomanip>
#include <stdio.h>
#include <queue>
#define int long long
//#define int __int128
using namespace std;
#define endl '\n'
#define F first
#define S second
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<string, int> psi;
const int N = 1e6 + 10;
const int mod = 1e9+9;
const int M = 8;
const int MAXN = 1e6;

//读入
inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while (ch > '9' || ch < '0') { if (ch == '-')f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
//打印
inline void write(int x) {
	if (x < 0) { putchar('-'); x = -x; }
	if (x > 9)write(x / 10);
	putchar(x % 10 + '0');
}

ll ksm(ll m,ll k,ll mod)
{
	ll ans=1;
	ll t=m;//通过t来预处理m的二次方幂
	while(k){
		if(k&1) ans=ans*t%mod;//判断k的二进制末位是否为1,相当于k%=2
		t=t*t%mod;//预处理
		k>>=1;//将k的二进制位右移相当于k/=2
	}
	return ans;
}

int phi(int a)
{
	int res=a;
	for(int i=2;i<=a/i;i++){
		if(a%i==0){
			res = res/i*(i-1);
			while(a%i==0) a/=i;
		}
	}
	if(a>1) res = res / a * (a - 1);
	return res;
}

void exgcd(int a,int b,int &x,int &y)
{
	if(b==0){
		x=1,y=0;
		return;
	}
	exgcd(b,a%b,y,x);//由于是使用指针传输，故可以在这里就交换x，y
	y-=(a/b)*x;//x,y已交换
}

int gcd(int a,int b)
{
	return b==0?a:gcd(b,a%b);
}

vector<int> a;
map<int,int> mp;
vector<int> ans;

void solve()
{
	int m,k;
	cin>>m>>k;
	int num=1;
	int sum=0;
	int ans=0;
	int ping=0;
	for(int i=1;i<=k;i++){
		ans=(ans+(ping+1)*m)%mod;
		sum=(((sum-ping)+(ping+1)*m)%mod+mod)%mod;
		num=(num+m-1)%mod;
		ping=sum*ksm(num,mod-2,mod)%mod;
	}
	cout<<ans<<endl;
}

signed main()
{
	std::ios::sync_with_stdio(false);//
	std::cin.tie(0);
	int tc;	
	//fac_init(mod);
	tc = 1;
	//cin >> tc;
	//scanf("%lld",&tc);
	while (tc--) {
		solve();
	}
	return 0;
}