#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(int)a;i<(int)b;i++)
#define all(p) p.begin(),p.end()
using ll =long long;

struct mint{
    static constexpr int  m = 1'000'000'009;
    int x;
    mint() : x(0){}
    mint(ll x_):x(x_%m){if(x<0) x+=m;}
    mint &operator+=(mint b){if((x+=b.x)>=m) x-=m; return *this;}
    mint &operator*=(mint b){x=(ll)(x)*b.x%m;return *this;}
    mint pow(ll e) const {
        mint r=1,b=*this;
        while(e){
            if(e&1) r*=b;
            b*=b;
            e>>=1;
        }
        return r;
    }
    mint inv(){return pow(m-2);}
    friend mint operator+(mint a,mint b){return a+=b;}
    friend mint operator*(mint a,mint b){return a*=b;}
};

void solve(){
    ll M,K;
    cin>>M>>K;
    vector<mint> A(K+1,1),B(K+1);
    rep(i,0,K) A[i+1]=A[i]*((M-1)*(i+1)+1);
    B[K]=A[K].inv();
    for(int i=K-1;i>=0;i--) B[i]=B[i+1]*((M-1)*(i+1)+1);
    mint P=0,L=0;
    rep(i,0,K){
        P+=M*(1+L);
        L+=A[i]*B[i+1]*M;
    }
    cout<<P.x<<"\n";
}

int main(){
    solve();
}