Untitled

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

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x...)
#endif

using ll = long long;
using db = long double;

constexpr int MOD = 1e9 + 7;

int sum(int a, int b) {
    return ((a += b) >= MOD ? a - MOD : a);
}

int prod(int a, int b) {
    return (ll)a * b % MOD;
}

vector<vector<int>> operator*(const vector<vector<int>> &a, const vector<vector<int>> &b) {
    assert(a[0].size() == b.size());
    vector<vector<int>> res(a.size(), vector<int>(b[0].size()));
    for (int i = 0; i < (int)a.size(); i++) {
        for (int j = 0; j < (int)b[0].size(); j++) {
            for (int k = 0; k < (int)a[0].size(); k++) {
                res[i][j] = sum(res[i][j], prod(a[i][k], b[k][j]));
            }
        }
    }
    return res;
}

vector<vector<int>> bin_pow(vector<vector<int>> a, ll power) {
    assert(a.size() == a[0].size());
    vector<vector<int>> res(a.size(), vector<int>(a.size()));
    for (int i = 0; i < (int)a.size(); i++) {
        res[i][i] = 1;
    }
    for (; power; power /= 2) {
        if (power & 1) res = res * a;
        a = a * a;
    }
    return res;
}

void test_case() {
    ll n;
    int m, k;
    cin >> n >> m >> k;
    vector<vector<int>> mt(m + 1, vector<int>(m + 1));
    for (int i = 0; i <= m; i++) {
        for (int j = max(0, i - k); j <= min(m, i + k); j++) {
            mt[i][j] = 1;
        }
    }
    vector<vector<int>> vec(m + 1, vector<int>(1, 1));
    vec = bin_pow(mt, n - 1) * vec;
    int ans = 0;
    for (int i = 0; i <= m; i++) {
        ans = sum(ans, vec[i][0]);
    }
    cout << ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tests = 1;
    // cin >> tests;
    while (tests--) {
        test_case();
    }
    return 0;
}