#include <bits/stdc++.h>
using namespace std;
void cal(long long s[2][2], long long t[2][2]) {
  long long tmp[2][2];
  memset(tmp, 0, sizeof(tmp));
  for (int k = 0; k < 2; k++)
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++) {
        tmp[i][j] = (tmp[i][j] + s[i][k] * t[k][j]) % 1000000009;
      }
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++) s[i][j] = tmp[i][j];
}
long long mul(long long cnt, long long k) {
  long long g[2][2];
  g[0][0] = 2;
  g[0][1] = 0;
  g[1][0] = 2 * k;
  g[1][1] = 1;
  long long tmp[2][2];
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++)
      if (i == j)
        tmp[i][j] = 1;
      else
        tmp[i][j] = 0;
  cnt--;
  while (cnt) {
    if ((cnt & 1) != 0) {
      cal(tmp, g);
    }
    cnt >>= 1;
    cal(g, g);
  }
  return (2 * k * tmp[0][0] + tmp[1][0]) % 1000000009;
}
int main() {
  int n, m, k;
  scanf("%d%d%d", &n, &m, &k);
  long long sum, tmp;
  tmp = n - m;
  if (tmp * (k) + k - 1 >= n) {
    printf("%d", m);
  } else {
    sum = tmp * (k - 1);
    tmp = n - tmp * k;
    long long cnt = tmp / k;
    sum += tmp - cnt * k;
    long long sum1 = k;
    sum1 = mul(cnt, sum1);
    sum = (sum + sum1) % 1000000009;
    cout << sum;
  }
  return 0;
}
