#include <bits/stdc++.h>
using namespace std;
template <typename T>
bool elem(set<T> st, T val) {
  return (st.find(val) != st.end());
}
using namespace std;
unsigned long long powM(unsigned long long a, unsigned long long n) {
  unsigned long long ret = 1;
  unsigned long long mul = a;
  while (n > 0) {
    if ((n & 1) == 1) {
      ret *= mul;
      ret %= 1000000009;
    }
    mul *= mul;
    mul %= 1000000009;
    n >>= 1;
  }
  return ret;
}
unsigned long long n, m, k;
unsigned long long seq(unsigned long long c) {
  unsigned long long n = c / k + 1;
  unsigned long long ret = 0;
  ret = ((powM(2, n) + 1000000009 - 2) * k) % 1000000009;
  ret += c % k;
  ret %= 1000000009;
  return ret;
}
int main(void) {
  cin >> n >> m >> k;
  unsigned long long miss = n - m;
  if (n <= (miss + 1) * k - 1) {
    cout << m % 1000000009 << endl;
    return 0;
  }
  unsigned long long c = n - miss * k;
  cout << (((k - 1) * miss % 1000000009) + seq(c)) % 1000000009 << endl;
  return 0;
}
