#include <bits/stdc++.h>

using namespace std;

const int md = 1000000009;
const long long mdmd = (long long) md * md;

const int N = 777;

int a[N][N], b[N][N], c[N][N];

int main() {
  long long s;
  int m, d;
  cin >> s >> m >> d;
  memset(a, 0, sizeof(a));
  for (int i = 0; i < m * m; i++) {
    if (i >= m) {
      a[i][i - m]++;
    } else {
      for (int j = 0; j < m; j++) {
        if (abs(i - j) <= d) {
          a[i][j * m + j]++;
        }
      }
    }
  }
  memset(b, 0, sizeof(b));
  for (int i = 0; i < m * m; i++) {
    b[0][i * m + i] = 1;
  }
  s--;
  while (s > 0) {
    if (s & 1) {
      for (int i = 0; i < m * m; i++) {
        for (int j = 0; j < m * m; j++) {
          long long sum = 0;
          for (int k = 0; k < m * m; k++) {
            sum += (long long) b[i][k] * a[k][j];
            if (sum >= mdmd) {
              sum -= mdmd;
            }
          }
          c[i][j] = sum % md;
        }
      }
      for (int i = 0; i < m * m; i++) {
        for (int j = 0; j < m * m; j++) {
          b[i][j] = c[i][j];
        }
      }
    }
    for (int i = 0; i < m * m; i++) {
      for (int j = 0; j < m * m; j++) {
        long long sum = 0;
        for (int k = 0; k < m * m; k++) {
          sum += (long long) a[i][k] * a[k][j];
          if (sum >= mdmd) {
            sum -= mdmd;
          }
        }
        c[i][j] = sum % md;
      }
    }
    for (int i = 0; i < m * m; i++) {
      for (int j = 0; j < m * m; j++) {
        a[i][j] = c[i][j];
      }
    }
    s >>= 1;
  }
  int ans = 0;
  for (int j = 0; j < m; j++) {
    ans = (ans + b[0][j]) % md;
  }
  printf("%d\n", ans);
  return 0;
}