#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e7;

const int MOD = 1e9+9;
struct mint
{
    int x;
    mint() : x(0) {}
    mint(int _x) : x(_x) {}
    mint operator + (int ot) const { return x+ot>=MOD ? x+ot-MOD : x+ot; }
    mint operator - () const { return x ? MOD-x : 0; }
    mint operator - (int ot) const { return x<ot ? x+MOD-ot : x-ot; }
    mint operator * (int ot) const { return 1ll*x*ot%MOD; }
    mint operator += (int ot) { return *this = *this + ot; }
    mint operator -= (int ot) { return *this = *this - ot; }
    mint operator *= (int ot) { return *this = *this * ot; }
    operator int () const { return x; }
};
mint mpow(mint x, ll a)
{
    mint ret=1;
    while(a)
    {
        if(a&1) ret*=x;
        x=x*x; a>>=1;
    }
    return ret;
}
mint inv(mint x) { return mpow(x, MOD-2); }

int M, K;
mint dp1[MAXN+10], dp2[MAXN+10];

int main()
{
    scanf("%d%d", &M, &K);
    for(int i=1; i<=K; i++)
    {
        mint t=inv((M-1)*(i-1)+1);
        dp1[i]=dp1[i-1]+dp1[i-1]*t*(M-1)+M;
        dp2[i]=dp2[i-1]+dp1[i-1]*t*M+M;
    }
    printf("%d\n", (int)dp2[K]);
}