#include <bits/stdc++.h>
using namespace std;
long long n, m, k, l, mid, p, r;
bool f(int x) {
  int out;
  out = x * (k - 1) + x - 1;
  if (m - x * (k - 1) > 0) out = out + m - x * (k - 1) + 1;
  if (out <= n)
    return 1;
  else
    return 0;
};
long long binpow(long long u, long long v) {
  if (v == 0) return 1;
  if (v % 2 == 0) {
    long long z = binpow(u, v / 2);
    return z * z % 1000000009;
  };
  return binpow(u, v - 1) * u % 1000000009;
};
int main() {
  cin >> n >> m >> k;
  l = 0;
  r = m / (k - 1);
  while (l < r) {
    if (l == r - 1) {
      if (f(r))
        l = r;
      else
        r = l;
      break;
    };
    mid = (l + r) / 2;
    if (f(mid))
      l = mid;
    else
      r = mid - 1;
  };
  p = m - l * (k - 1);
  r = p / k;
  cout << ((binpow(2, r + 1) - 2) * k % 1000000009 + p % k + m - p +
           1000000009) %
              1000000009;
  return 0;
}
