#include <bits/stdc++.h>
using namespace std;
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T>
inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}
template <class T>
inline T sqr(T x) {
  return x * x;
}
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, 1, -1};
const long long MOD = 1000000009;
long long ans, ret;
long long n, m, k, mis, mi;
long long mop(long long x, long long kai) {
  long long res = 1;
  while (kai > 0) {
    if (kai & 1) res = res * x % MOD;
    x = x * x % MOD;
    kai /= 2;
  }
  return res;
}
int main() {
  cin >> n >> m >> k;
  mis = n - m;
  mi = min(mis, m / (k - 1));
  ret = mi * (k - 1) % MOD;
  n -= k * mi;
  m -= (k - 1) * mi;
  mis -= mi;
  if (mis == 0) {
    long long za = m / k, ama = m % k;
    if (za > 0) {
      ans = (mop(2LL, za + 1) - 2LL + MOD) % MOD * k % MOD;
    }
    ans += ama;
    ans %= MOD;
  } else {
    ans = m;
    ans %= MOD;
  }
  cout << (ans + ret) % MOD << endl;
  return 0;
}
