#include <bits/stdc++.h>

template <bool flag, typename T1, typename T2>
struct TemplateIf;
template <typename T1, typename T2>
struct TemplateIf<true, T1, T2> { using Type = T1; };
template <typename T1, typename T2>
struct TemplateIf<false, T1, T2> { using Type = T2; };

using i32 = int32_t;
using i64 = int64_t;
using i128 = __int128_t;
using u32 = uint32_t;
using u64 = uint64_t;
using u128 = __uint128_t;
template <typename T>
using Vec = std::vector<T>;
template <typename T, size_t... other>
struct ArraySwitch;
template <typename T, size_t size, size_t... other>
struct ArraySwitch<T, size, other...> { using Result = std::array<typename ArraySwitch<T, other...>::Result, size>; };
template <typename T, size_t size>
struct ArraySwitch<T, size> { using Result = typename std::array<T, size>; };
template <typename T, size_t... size>
using Arr = typename ArraySwitch<T, size...>::Result;
template <typename T>
using MaxHeap = std::priority_queue<T, Vec<T>, std::less<T>>;
template <typename T>
using MinHeap = std::priority_queue<T, Vec<T>, std::greater<T>>;			

constexpr i32 inf32 = (i32)(1e9) + 9;
constexpr i64 inf64 = (i64)(1e18) + 18;

std::mt19937 rng { (std::random_device())() };

template <typename T>
inline T makeVec(T val) { return val; }
template <typename T, typename... Args>
inline auto makeVec(T val, size_t size, Args... rest) {
    auto t = makeVec<T>(val, rest...);
    return Vec<decltype(t)>(size, t);
}

inline i32 clz(u32 x) { return __builtin_clz(x); }
inline i32 clzll(u64 x) { return __builtin_clzll(x); }
inline i32 ctz(u32 x) { return __builtin_ctz(x); }
inline i32 ctzll(u64 x) { return __builtin_ctzll(x); }
inline i32 popcount(u32 x) { return __builtin_popcount(x); }
inline i32 popcountll(u64 x) { return __builtin_popcountll(x); }

template <typename T>
inline T _min(T a) { return a; }
template <typename T, typename... Args>
inline T _min(T a, T b, Args... args) { return _min<T>(std::min<T>(a, b), args...); }
template <typename T>
inline T _max(T a) { return a; }
template <typename T, typename... Args>
inline T _max(T a, T b, Args... args) { return _max<T>(std::max<T>(a, b), args...); }

constexpr i32 num_big_primes = 10;
constexpr Arr<i32, num_big_primes> big_primes { 99990571, 99990337, 99999941, 99999931, 99999847, 99999839, 99999827, 99999821, 99999787, 99999773, };
inline i32 get_big_prime() { return big_primes[std::uniform_int_distribution<i32>(0, num_big_primes - 1)(rng)]; }

constexpr i32 mod = i32(1e9) + 9;

constexpr i32 power(i32 n, i32 m) {
    i32 res = 1;
    while (m) {
        if (m & 1) {
            res = 1ll * res * n % mod;
        }
        n = 1ll * n * n % mod;
        m >>= 1;
    }
    return res;
}
constexpr i32 inv_2 = power(2, mod - 2);

i32 main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    i32 n, m;
    std::cin >> n >> m;
    i32 t = 1ll * (n - 1) * n % mod * inv_2 % mod;
    i32 ans = 1;
    for (i32 i = 1; i <= n; i++) ans = 1ll * ans * i % mod;
    for (i32 i = 1; i <= m; i++) {
        ans = 1ll * ans * t % mod;
        ans = 1ll * ans * power(i, mod - 2) % mod;
        t = (t - 1) % mod;
    }
    ans = (ans + mod) % mod;
    std::cout << ans << std::endl;
    std::cerr << "use time: " << 1. * std::clock() / CLOCKS_PER_SEC << std::endl;
    return 0;
}