#include<iostream>
#include<algorithm>
using namespace std;
long long mod=1e9+9;
long long pow(long long a,long long b=mod-2){
    if(b==0)return 1;
    if(b==1)return a;
    long long ret=pow(a,b>>1);
    if(b&1)return ret*ret%mod*a%mod;
    else return ret*ret%mod;
}
long long E=0;
int main(){
    // cout<<24*pow(3)%mod<<endl;
    long long m,k,Kl=1,El=0;
    cin>>m>>k;
    while(k--){
        // cout<<El*6%mod<<" "<<E*3%mod<<"?"<<Kl<<endl;
        E=(E+(El+1)*m)%mod;
        El=(El*(Kl-1)+m*(El+1))%mod*pow(Kl+m-1)%mod;
        Kl+=m-1;
    }
    cout<<E<<endl;
}