#include<bits/stdc++.h>
using namespace std;

using i64 = long long;

const i64 P = 1e9+9;
const int N = 1e7+7;

int m,k;
i64 f[N],g[N];

i64 ksm(i64 x,int cs){
    i64 sum=1;
    while(cs){
        if(cs%2)
            sum=sum*x%P;
        x=x*x%P;
        cs/=2;
    }
    return sum;
}

i64 leaf(i64 x){
    return (x*m%P-x+P+1)%P;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>m>>k;
    for(int i=1;i<=k;i++){ 
        i64 x=ksm(leaf(i-1),P-2);
        f[i]=(f[i-1]+m*(1+g[i-1]*x%P)%P)%P;
        g[i]=((g[i-1]+(m-1)*g[i-1]%P*x%P)%P+m)%P;
    }
    cout<<f[k];
    return 0;
}