#include <bits/stdc++.h>
using namespace std;
unsigned long long p2u(unsigned long long u) {
  if (u == 0) return 1;
  if (u == 1) return 2;
  unsigned long long v = p2u(u / 2);
  v %= 1000000009;
  v *= v;
  v %= 1000000009;
  if (u % 2) {
    v *= 2;
    v %= 1000000009;
  }
  return v;
}
int main() {
  unsigned long long n, m, k;
  cin >> n >> m >> k;
  unsigned long long km = k * m, vn = (k - 1) * n,
                     y = (km < vn) ? 0 : (km - vn) / k, pu = p2u(y + 1),
                     qu = pu < 2 ? pu + 1000000009 - 2 : pu - 2,
                     r = k * qu + (m - k * y);
  cout << (r % 1000000009) << endl;
  return 0;
}
