#include<bits/stdc++.h>
#define mod 1000000009u
using namespace std;
long long m,k;
int ima[10000007], imb[10000007];
struct barrett{
	unsigned long long im;int m;
	barrett(unsigned m) :m(m), im(~0ull/m+1) {}
	inline int operator ()(int a,int b){
		unsigned long long z=(unsigned long long)a*b;
		int v = z - ((__int128)z * im >> 64) * m;
		return v<0?v+m:v;
	}
}bt(1);
array<int, 4> mi_vec(vector<int> a, int b=mod-2){
    array<int, 4> ans({1,1,1,1});
    while(b){
        if(b&1){
            ans[0] = bt(ans[0], a[0]);
            ans[1] = bt(ans[1], a[1]);
            ans[2] = bt(ans[2], a[2]);
            ans[3] = bt(ans[3], a[3]);
            // ans[0]=1ll*ans[0]*a[0]%mod;
            // ans[1]=1ll*ans[1]*a[1]%mod;
            // ans[2]=1ll*ans[2]*a[2]%mod;
            // ans[3]=1ll*ans[3]*a[3]%mod;
        }
        b>>=1;
        a[0] = bt(a[0], a[0]);
        a[1] = bt(a[1], a[1]);
        a[2] = bt(a[2], a[2]);
        a[3] = bt(a[3], a[3]);

    }
    // cerr << "T:\n";
    return ans;
}
int mi(int a,int b=mod-2){
    // return 1;
    int ans=1;
    while(b){
        if(b&1) ans=1ll*ans*a%mod;
        b>>=1;a=1ll*a*a%mod;
    }
    return ans;
}
int main(){
    scanf("%lld%lld",&m,&k);
    bt = barrett(mod);
    double start = clock();
    long long nw=0,lf=0;
    int i=1;
    for(i=1;i+4<k;i+=4){
        // cerr << "W:" << '\n';
        memcpy(ima + i, mi_vec({
            (i + 0) * m + 1,
            (i + 1) * m + 1,
            (i + 2) * m + 1,
            (i + 3) * m + 1,
        }).data(), 4 * 4);
        memcpy(imb + i, mi_vec({
            1 + (i + 0) * (m - 1),
            1 + (i + 1) * (m - 1),
            1 + (i + 2) * (m - 1),
            1 + (i + 3) * (m - 1),
        }).data(), 4 * 4);
    }
    for(;i<=k;i++){
        ima[i] = mi(i * m + 1);
        imb[i] = mi(1 + i * (m - 1));
    }
    for(int i=1;i<=k;++i){
        nw=(1ll*(lf+1)*m+1ll*nw*(1+(i-1)*m))%mod* ima[i] %mod;
        lf+=1ll*m* imb[i] %mod;lf%=mod;
    }
    nw=nw*(1+1ll*k*m)%mod;
    printf("%lld\n",nw);
    cerr << "time:" << clock() - start << '\n';
    return 0;
}