#include <string.h>
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

constexpr int mod = 1000000009;

void mpl(int &x,int y) {
    x += y;
    if(x >= mod) x -= mod;
}

long long modpow(long long a,long long b) {
    long long ans = 1;
    while(b) {
        if(b & 1) {
            (ans *= a) %= mod;
        }
        (a *= a) %= mod;
        b /= 2;
    }
    return ans;
}

int dp[10010010];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int M,K;
    cin >> M >> K;
    int ans = 0;
    for(int i = K; i >= 1; i--) {
        if(i == K) {
            mpl(ans,M);
            continue;
        }
        int res = 1+(M-1)*i;
        int inv = modpow(res,mod-2);
        mpl(dp[i],1ll*dp[i+1]*(mod+1-inv)%mod);
        mpl(dp[i],(1ll*dp[i+1]*M%mod+M)*inv%mod);
        mpl(ans,1ll*(dp[i]+1)*M%mod);
    }
    cout << ans << "\n";
}