#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int mod=1e9+9;

int pow(int a,int b=mod-2){
    if(b==0)return 1;
    if(b==1)return a;
    int ret=pow(a,b>>1);
    if(b&1)return (ll)ret*ret%mod*a%mod;
    else return (ll)ret*ret%mod;
}

int E=0;
int main(){
    int m,k,Kl=1,El=0;
    cin>>m>>k;
    while(k--){
        E=(E+(ll)(El+1)*m)%mod;
        El=((ll)El*(Kl-1)+(ll)m*(El+1))%mod*pow(Kl+m-1)%mod;
        Kl+=m-1;
    }
    cout<<E<<endl;
}