#include <bits/stdc++.h>

using namespace std;


typedef long long                               ll;
typedef unsigned long long                      ull;
#define int                                     long long
#define itn                                     int
#define endl                                    '\n'
#define Endl                                    endl
#define ednl                                    endl
#define al(a)                                   (a).begin(),(a).end()
#define all(a)                                  (a).begin()+1,(a).end()
#define debug(x)                                {cerr<<"ss:"<<x<<endl;}
#define qdebug(x)                               {cerr<<"ss:";for(auto i:x)cout<<i<<" ";cout<<endl;}
#define lowbit(x)                               (x&-x)
#define vi                                      vector<int>
#define pii                                     pair<int,int>
#define pb                                      push_back
#define fs                                      first
#define sc                                      second

constexpr long long maxlonglong = 9223372036854775807;   //9e18
constexpr int maxint = 2147483647;      //2e9
constexpr int INF = 0x7f7f7f7f7f7f7f7f; //2139062143^2
constexpr int M = 1e9 + 7;
constexpr int mod =  998244353;
constexpr int hs = 0x1F351F35; // good hash number.
const double pi = acos(-1.0);
const double eps = 1e-15;
vector<int> input(int n){vector<int> a(n+1);for(int i=1;i<=n;i++)cin>>a[i];return a;}
mt19937_64 rnd(time(0));

const int maxn=1e5+5;
constexpr int N=1231564;
const int p = 1e9+9;

int ksm(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b&1)ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}

inline void solve(){
    int m,k;cin>>m>>k;
    int ans=0,tot=1,con=0;
    for(int i=1;i<=k;i++)
    {
        ans=(ans+(con+1)*m%p)%p;
        con=(con*(tot+m-1)+m)%p*ksm(tot+m-1,p-2)%p;
        tot+=m-1;
    }
    cout<<ans%p<<"\n";
}





signed main()
{
    //freopen("E:\\work_tool\\document\\data\\input.in", "r", stdin);
    //freopen("E:\\work_tool\\document\\data\\output.out", "w", stdout);
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);    //关闭同步  如果使用 则不要使用<cstdio>
    // cout << fixed << setprecision(10);
    int T=1;
    // cin>>T;
    while(T--){
        solve();
    }
    return 0;
}