#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+9;
int M,K;
inline int qm(int x) {return x>=mod?x-mod:x;}
inline int ksm(int a,int b) {
    int S=1;for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) S=1ll*S*a%mod;return S;
}
int main() {
    scanf("%d%d",&M,&K);
    if(M==1) {
        printf("%lld\n",(1ll*K*(K+1)/2)%mod);
        return 0;
    }
    int pre = 0;
    int sz = 1;
    for(int i=1;i<=K;++i) {
        int num = 1 + (i-1)*(M-1);
        int now =  qm(qm(1ll*pre*(M-1)%mod + 1ll*sz*M%mod*num%mod) + 1ll*pre*num%mod);
        sz = 1ll*sz*num%mod;
        pre = now;
        //cout<<now<<" "<<sz<<" " <<pre<<endl;
    }
    int dep_s = 1ll*pre*ksm(sz,mod-2)%mod;
    //cout<<sz<<" "<<dep_s<<endl;
    dep_s = (dep_s - 1ll*K*M%mod + mod)%mod;
    dep_s = 1ll*dep_s*ksm(M-1,mod-2)%mod;
    printf("%d\n",qm(1ll*dep_s*M%mod + 1ll*K*M%mod));
    return 0;
}