#include <bits/stdc++.h>
using namespace std;
long long r = 1000000009;
int main() {
  long long m, n, k;
  cin >> n >> m >> k;
  long long d = n % k;
  d += (n / k) * (k - 1);
  if (m <= d) {
    cout << m % r;
    return 0;
  }
  int s = m - d;
  long long sc = (m - s * k) % r;
  long long c = 2;
  if (s < 100000000) {
    for (int i = s; i > 0; i--) {
      sc = (c * k + sc) % r;
      c = (c * 2) % r;
    }
  } else {
    while (s >= 10) {
      c = (c * 1024) % r;
      s -= 10;
    }
    while (s > 0) {
      c = (c * 2) % r;
      s--;
    }
    if (c >= 2) {
      c -= 2;
    } else {
      c += r;
      c -= 2;
    }
    c = (c * k) % r;
    sc = (sc + c) % r;
  }
  cout << sc;
  return 0;
}
