#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N=505;
const ll mod=1e9+9;
#define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++)
ll a[N];
int m,k;
ll ksm(ll a,ll b){
    int ans=1;
    for(;b;b>>=1){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
    }
    return ans;
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cin>>m>>k;
    ll a=0,b=0,cnt=1,dqfm=1;
    For(i,1,k){
        b=(b+a*m+m*dqfm)%mod;
        a=(a*cnt+a*(m-1)+m*dqfm)%mod;
        b=b*(cnt+m-1)%mod;
        dqfm=dqfm*(cnt+m-1)%mod;
        //cerr<<a<<" "<<b<<endl;
        cnt+=m-1;
    }
    cout<<b*ksm(dqfm,mod-2)%mod<<endl;
    return 0;
}