#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef long long ll;
#define N 10000007
#define F first
#define S second
#define mod 1000000009
int m,k,n=1,s=0,e=0;
inline int qpow(int a,int b){
    int ret = 1;
    while(b){
        if(b&1)ret=1ll*ret*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return ret;
}
inline int mod1(int x){return x>mod?x-mod:x;}
inline int mod2(int x){return x<0?x+mod:x;}

int main(){
    int t;
    scanf("%d%d",&m,&k);
    for(int i=1;i<=k;++i){
        t=1ll*e*qpow(n,mod-2)%mod;
        e=mod1(mod2(e-t)+1ll*(t+1)*m%mod);
        s=mod1(s+1ll*(t+1)*m%mod);
        n+=m-1;
        //printf("%lld %lld %lld\n",t,e,s);
    }
    printf("%d\n",s);
    return 0;
}