#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e7;
const int mod=1e9+9;
int ksm(ll x,int tp,int s=1){
    for(;tp;x=x*x%mod,tp>>=1) if(tp&1) s=x*s%mod;
    return s;
}
int n,m;
int val[N+5];
int pre[N+5],iv[N+5];
int f[N+5],g[N+5];
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
        val[i]=i*(n-1)+1;
    pre[0]=1;
    for(int i=1;i<=m;i++)
        pre[i]=1ll*val[i]*pre[i-1]%mod;
    iv[m]=ksm(pre[m],mod-2);
    for(int i=m;i;i--)
        iv[i-1]=1ll*iv[i]*val[i]%mod;
    for(int i=m;i;i--){
        iv[i]=1ll*pre[i-1]*iv[i]%mod;
        // printf("%d ",iv[i]);
    }
    // puts("");
    for(int i=1;i<=m;i++){
        f[i]=(f[i-1]+1ll*(g[i-1]+1)*n)%mod;
        g[i]=(1ll*g[i-1]*(i-1)*(n-1)+1ll*(g[i-1]+1)*n)%mod*iv[i]%mod;
        // printf("%d %d\n",f[i],g[i]);
    }
    printf("%d\n",f[m]);
    return 0;
}