mwj2020el1b

/* <copy-pasted-part> */
#pragma GCC optimize("Ofast,fast-math,unroll-loops")

#include <bits/stdc++.h>

#define int ll
//#define double long double
#define endl '\n'
#define all(C) (C).begin(), (C).end()
#define rall(C) (C).rbegin(), (C).rend()
#define mp make_pair
#define pb emplace_back
#define dbg(x) cerr << #x << " : " << x << endl
#define PI 3.14159265358979

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair <int, int>;
using pld = pair <ld, ld>;

/*
const ll MAX_MEM = 3e8;
char MEM[MAX_MEM];
ll MEM_POS = 0;
void* operator new(size_t x)
{
    auto ret = MEM + MEM_POS;
    MEM_POS += x;
    assert(MEM_POS < MAX_MEM);
    return ret;
}
void operator delete(void*)
{}
*/

template <class T>
istream& operator>> (istream &in, vector <T> &a)
{
    for (auto &i : a)
        in >> i;
    return in;
}

template <class T>
ostream& operator<< (ostream &out, vector <T> a)
{
    for (auto &i : a)
        out << i << ' ';
    return out;
}

template <class T, class U>
istream& operator>> (istream &in, pair <T, U> &p)
{
    in >> p.first >> p.second;
    return in;
}

template <class T, class U>
ostream& operator<< (ostream &out, pair <T, U> p)
{
    out << p.first << " " << p.second << " ";
    return out;
}

inline void Start()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
}
/* </copy-pasted-part> */

const int P = 1e9 + 9;
int add(int a, int b)
{
    return (a + b) % P;
}
int mul(int a, int b)
{
    return (a * b) % P;
}
struct comb
{
    vector <vector <int>> c;
    comb() {}
    comb(int n)
    {
        c.resize(n + 1, vector <int> (n + 1));
        c[0][0] = 1;
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 0; j < n + 1; ++j)
            {
                c[i][j] = add(c[i - 1][j], j ? c[i - 1][j - 1] : 0);
            }
        }
    }
    int operator() (int n, int k)
    {
        return c[n][k];
    }
};
int solve(int n, int m, int k)
{
    vector <vector <int>> dp(m / k + 1, vector <int> (2));
    dp[0][0] = 1;
    dp[1][1] = 1;
    dp[1][0] = n - k + 1;
    comb c(2000);
    dbg(c(18, 9));
    for (int i = 2; i <= m / k; ++i)
    {
        for (int j = 0; j < i; ++j)
            dp[i][0] = add(dp[i][0], mul(mul(add(dp[j][1], dp[j][0]), (n - k + 1)), c(k + i - j - 3, k - 2)));
        for (int j = 0; j < i; ++j)
            dp[i][1] = add(dp[i][1], dp[j][0]);
    }
    return add(dp[m / k][0], dp[m / k][1]);
}

signed main()
{
    Start();
    int n, m, k;
    cin >> n >> m >> k;
    if (m % k != 0)
    {
        if (n != k)
            return cout << 0, 0;
        vector <int> dp(m + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= m; ++i)
        {
            dp[i] = add(dp[i - 1], (i - k >= 0 ? dp[i - k] : 0));
        }
        cout << dp[m];
        return 0;
    }
    if (k == 1)
        return cout << 1, 0;
    if (k > n)
    {
        return cout << 1, 0;
    }
    cout << solve(n, m, k);
    return 0;
}