#include <bits/stdc++.h>
std::map<uint64_t, uint64_t> cache;
uint64_t f2pow(uint64_t b) {
  if (b == 0) return 1;
  if (b == 1) return 2;
  auto it = cache.find(b);
  if (it != cache.end()) return it->second;
  unsigned int f = b / 2;
  cache[b] = (f2pow(f) * f2pow(b - f)) % 1000000009;
  return cache[b];
}
uint64_t solve() {
  uint64_t questionC, corrC, compo;
  std::cin >> questionC >> corrC >> compo;
  uint64_t groupCount = questionC / compo;
  uint64_t easy = groupCount * (compo - 1) + questionC % compo;
  if (easy >= corrC) return corrC;
  corrC -= easy;
  return ((2 * compo * (f2pow(corrC) - 1)) + (easy - corrC * (compo - 1))) %
         1000000009;
}
int main() {
  std::cout << solve() << std::endl;
  return 0;
}
