#include <bits/stdc++.h>
using namespace std;
int k, n, m;
int main(void) {
  long long sc;
  long long t;
  long long s, x;
  cin >> n >> m >> k;
  if (n - m >= n / k) {
    cout << m << endl;
    return 0;
  }
  t = (n - (n - m) * k) / k;
  t++;
  sc = n % k + (n - m) * (k - 1);
  s = 1;
  x = 2;
  while (t) {
    if (t & 1) {
      s *= x;
      s %= 1000000009;
    }
    x *= x;
    x %= 1000000009;
    t >>= 1;
  }
  sc += (k * s - k * 2) % 1000000009;
  cout << (sc + 1000000009) % 1000000009 << endl;
  return 0;
}
