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

#define TRACE(x) cerr << __LINE__ << ": " << #x << " = " << x << endl
#define _ << " _ " <<

template<class T, class U>
ostream& operator<<(ostream &o, pair<T, U> x) {
  return o << "(" << x.first << ", " << x.second << ")";
}
template<class> struct is_container : false_type {};
template<class... Ts> struct is_container<vector<Ts...>> : true_type {};
template<class... Ts> struct is_container<map<Ts...>> : true_type {};
template<class... Ts> struct is_container<unordered_map<Ts...>> : true_type {};
template<class... Ts> struct is_container<set<Ts...>> : true_type {};
template<class... Ts> struct is_container<unordered_set<Ts...>> : true_type {};
template<class... Ts> struct is_container<multiset<Ts...>> : true_type {};
template<class... Ts> struct is_container<unordered_multiset<Ts...>> : true_type {};
template<class T, class = typename enable_if<is_container<T>::value>::type>
ostream& operator<<(ostream &o, T x) {
  int f = 1;
  o << "{";
  for (auto y : x) {
    o << (f ? "" : ", ") << y;
    f = 0;
  }
  return o << "}";
}

#define fi first
#define se second
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

const int MOD = 1e9 + 9;
int add(int a, int b) { 
    a += b;
    if (a >= MOD) a -= MOD;
    return a;
}
int sub(int a, int b) { return add(a, MOD - b); }
int mul(int a, int b) { return (ll)a * b % MOD; }
int pwr(int a, int b) {
    int res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = mul(res, a);
        a = mul(a, a);
    }
    return res;
}
int inv(int a) { return pwr(a, MOD - 2); }

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int M, K;
    cin >> M >> K;

    int sum_leaves = 0, sum = 0, cnt_leaves = 1;
    for (int i = 0; i < K; i++) {
        int d = mul(sum_leaves, inv(cnt_leaves));
        sum = add(sum, mul(M, d + 1));
        sum_leaves = add(sum_leaves, sub(mul(M, d + 1), d));
        cnt_leaves += M - 1;
    }
    cout << sum << '\n';

    return 0;
}

// d -> doda M*(d+1)-d = (M-1)d + M na sumu dubina listova
//      doda M*(d+1) na sumu dubina svih
// nakon k imamo 1 + (M-1)k listova