#include <bits/stdc++.h>
using namespace std;
int64_t modpow(int64_t x, int64_t p, int64_t m) {
  if (p == 0)
    return 1;
  else if (p == 1)
    return x;
  else if (p % 2 == 0)
    return modpow((x * x) % m, p / 2, m);
  else
    return (x * modpow((x * x) % m, (p - 1) / 2, m)) % m;
}
int main() {
  int64_t n, m, k;
  cin >> n >> m >> k;
  int64_t wod = n / k * (k - 1);
  wod += n % k;
  if (wod >= m) {
    cout << m;
    return 0;
  }
  int64_t total = 0;
  int64_t doublings = (m - wod);
  total += (modpow(2, doublings + 1, 1000000009) - 2) * k;
  total += m - doublings * k;
  ;
  total %= 1000000009;
  if (total < 0) total += 1000000009;
  cout << total << endl;
}
