#include <bits/stdc++.h>
using namespace std;
int INP, AM, REACHEOF;
const int BUFSIZE = (1 << 12) + 17;
char BUF[BUFSIZE + 1], *inp = BUF;
const long long MOD = 1000000009LL;
long long power(long long x, long long k) {
  if (k == 0) return 1;
  if (k == 1) return x % MOD;
  long long mid = power(x, k >> 1);
  mid = mid * mid % MOD;
  if (k & 1)
    return mid * x % MOD;
  else
    return mid;
}
int main() {
  ios ::sync_with_stdio(false);
  long long all, correct, k;
  while (cin >> all >> correct >> k) {
    long long wrong = all - correct;
    long long nGroup = correct / (k - 1);
    if (correct % (k - 1)) ++nGroup;
    if (wrong >= nGroup - 1) {
      cout << correct << endl;
    } else {
      long long left = 0, right = nGroup, res = nGroup;
      while (left <= right) {
        long long mid = (left + right) >> 1;
        long long nGroup = (correct - mid * k) / (k - 1);
        if ((correct - mid * k) % (k - 1)) ++nGroup;
        if (wrong >= nGroup - 1) {
          res = mid;
          right = mid - 1;
        } else
          left = mid + 1;
      }
      long long mult = (power(2, res + 1) - 2 + MOD) % MOD;
      cout << ((mult * k) + (correct - res * k)) % MOD << endl;
    }
  }
  return 0;
}
