#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;

typedef long long ll;
#define int ll

#define fi first
#define se second
#define pb push_back

typedef long double ld;
#define double  ld

const int mod = 1e9+9;

int bpow(int a, int b)
{
    int r = 1;
    while (b > 0)
    {
        if (b&1)
            r = r*a%mod;
        a = a*a%mod;
        b/=2;
    }
    return r;
}
int inv(int a)
{
    return bpow(a, mod-2);
}

signed main()
{
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

    int M, K;
//    M = 6;
//    K = 2;

    cin>>M>>K;
    int iM = inv(M);
    int n = 1;
    int s = 0;
    for (int i=0; i<K; i++)
    {
        int up = (s*(1-iM)+n)%mod*M%mod;
        int down = ((n-1)*(M-1)%mod*iM+1)%mod;
//        cout<<up<<"/"<<down<<"\n";

        int ds = up*inv(down)%mod;
        s = (s+ds)%mod;
        s = (s+mod)%mod;
        n = (n+M)%mod;

//        cout<<n<<" "<<s<<"\n";
    }
    cout<<s<<"\n";
}