#include <bits/stdc++.h>
int n, m;
long long k;
long long pow(int n) {
  if (n == 0) return 1;
  long long tmp = pow(n >> 1);
  tmp = tmp * tmp % 1000000009ll;
  if (n & 1) tmp = tmp * 2ll % 1000000009ll;
  return tmp;
}
int main() {
  scanf("%d%d%I64d", &n, &m, &k);
  int t = n - m;
  long long ans = 0;
  if (m == 0) {
    puts("0");
    return 0;
  }
  if (n - t * k < k) {
    ans = m;
  } else {
    int num = (n - t * k) / k;
    ans = (pow(num + 1) - 2 + 1000000009ll) * k % 1000000009ll;
    ans = (ans + (n - t * k) % k) % 1000000009ll;
    ans = (ans + t * (k - 1)) % 1000000009ll;
  }
  printf("%I64d\n", ans);
  return 0;
}
