#include <bits/stdc++.h>
using namespace std;
long long quickpow(long long i) {
  long long res = 1, now = 1;
  while (i) {
    if (now == 1)
      now = 2;
    else
      now *= now;
    now %= 1000000009;
    if (i & 1) {
      res *= now;
      res %= 1000000009;
    }
    i /= 2;
  }
  return res;
}
int main() {
  long long n, m, k;
  cin >> n >> m >> k;
  long long err = n - m;
  if (err * k >= n) {
    cout << m << endl;
    return 0;
  }
  long long con = n - err * k;
  long long k1 = con % k;
  long long k2 = con / k;
  long long res = quickpow(k2 + 1);
  res -= 2;
  res *= k;
  res %= 1000000009;
  res = res + k1 + err * (k - 1) + 1000000009;
  res %= 1000000009;
  cout << res << endl;
  return 0;
}
