#define _CRT_SECURE_NO_WARNINGS // 关闭编译器中不安全函数的警告
#include <iostream>
#include <vector>
using namespace std;

#define LL long long // 定义长整型
const int N = 1e7 + 100; // 定义数组大小，最大支持1000万
const LL mod = 1e9 + 9; // 定义模数
const LL INF = 1e18; // 定义长整型的无穷大
LL f[N], a; // 定义数组 f 和变量 a
LL m, k, x; // m 表示某个值，k 表示某个阈值，x 为中间变量

// 快速幂函数，用于快速计算 (a^b) % mod
LL quick(LL a, LL b, LL mod) {
    LL ans = 1;
    while (b) { // 当 b 不为 0 时
        if (b & 1) ans = ans * a % mod; // 如果 b 的二进制表示的最低位是 1，则将当前的 a 乘入结果中
        b >>= 1; // b 右移一位，相当于 b 除以 2
        a = a * a % mod; // 计算 a 的平方并取模
    }
    return ans;
}

int main() {
    // 输入 m 和 k，m 表示要处理的某个值，k 表示限制的次数
    cin >> m >> k;
    
    // 设定初始条件 f[k] = 1
    f[k] = 1;

    // 从 k-1 开始逆向计算 f[i]，其中每一步计算与 (m - 1) 和 i 有关
    for (LL i = k - 1; i >= 0; i--) 
        f[i] = f[i + 1] * ((m - 1) * i % mod + 1) % mod;

    // 计算 x 为 f[0] 的模逆元
    x = f[0];
    x = quick(x, mod - 2, mod); // 利用费马小定理计算模逆元

    LL ans = 0; // 用于存储最终的答案
    a = 0; // 辅助变量 a 用于存储中间计算结果

    // 从 0 到 k-1 的循环，用于逐步累加结果
    for (LL i = 0; i <= k - 1; i++) {
        // 更新 ans，使用当前的 x 和 f[i+1] 进行相关的计算
        ans = (ans + a * x % mod * f[i + 1] % mod + 1) % mod;

        // 更新 a，计算与 m 和 f[i+1] 有关的表达式，并模上 mod
        a = (a * x % mod * f[i + 1] % mod * ((i + 1) * (m - 1) % mod + 1) % mod + m) % mod;

        // 更新 x，递归地调整 x 的值
        x = x * (i * (m - 1) % mod + 1) % mod;
    }

    // 最后将结果乘以 m，并取模
    ans = ans * m % mod;

    // 输出最终结果
    cout << ans << endl;
    return 0;
}