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

#define int long long
const int N = 1e7+10, mod = 1e9+9;
int M, K, P, pre[N], suf[N];

int fpow(int x, int y){
    int z = 1;
    while(y){
        if(y&1) z = (z*x)%mod;
        x = (x*x)%mod;
        y >>= 1;
    }
    return z;
}
int inv(int x){
    return fpow(x, mod-2);
}
signed main(){
    ios :: sync_with_stdio(false);
    cin >> M >> K;
    pre[0] = 1; suf[K] = 1;
    for(int i = 1; i <= K-1; i++)
        pre[i] = (pre[i-1]*(i*(M-1)+1))%mod;
    for(int i = K-1; i >= 1; i--)
        suf[i] = (suf[i+1]*(i*(M-1)+1))%mod;
    P = inv(pre[K-1]);
    int sum = 0;
    for(int i = 1; i < K; i++){
        int d = P*pre[i-1]%mod*suf[i+1]%mod;
        sum = (sum+(K-i)*d)%mod;
    }
    sum = ((K*M)%mod+(M*M)*sum%mod)%mod;
    cout << sum << endl;
    return 0;
}