#include <bits/stdc++.h>
using namespace std;
int bit[40];
int n, m, k;
void init() {
  int i;
  for (bit[0] = 2, i = 1; i <= 30; ++i)
    bit[i] = ((long long)bit[i - 1] * (long long)bit[i - 1]) % 1000000009;
}
void conduct() {
  int tmp, t, ans, i;
  scanf("%d%d", &m, &k);
  t = m + n / k - n;
  if (t < 0) {
    printf("%d\n", m);
    return;
  }
  for (tmp = 1, i = 0; i <= 30; ++i)
    if ((1 << i) & (t + 1))
      tmp = ((long long)tmp * (long long)bit[i]) % 1000000009;
  tmp = (tmp + 1000000009 - 2) % 1000000009;
  tmp = ((long long)tmp * (long long)k) % 1000000009;
  ans = ((long long)tmp + (long long)m - (long long)t * k) % 1000000009;
  printf("%d\n", ans);
}
int main() {
  init();
  while (scanf("%d", &n) != EOF) conduct();
  return 0;
}
