#include <bits/stdc++.h>
const int MOD = 1000000009;
long long pow(int n) {
  long long ret = 1;
  long long b = 2;
  while (n) {
    if (n % 2) {
      ret *= b;
      ret %= MOD;
    }
    n /= 2;
    b = (b * b) % MOD;
  }
  return ret;
}
int main() {
  int n, m, k;
  scanf("%d%d%d", &n, &m, &k);
  long long total = (long long)(n - m) * k;
  long long ret = 0;
  if (total >= n)
    printf("%d\n", m);
  else {
    ret += (long long)(n - m) * (k - 1) % MOD;
    ret %= MOD;
    int left = (n - total);
    ret += (left % k);
    ret %= MOD;
    int temp = (left / k);
    ret += ((long long)2 * k % MOD) * ((pow(temp) + MOD - 1) % MOD) % MOD;
    ret %= MOD;
    printf("%I64d\n", ret);
  }
  return 0;
}
