#include <bits/stdc++.h>
long long pw(long long x) {
  if (x == 0) return 1;
  if (x % 2 == 1) return 2 * pw(x - 1) % 1000000009LL;
  return pw(x / 2) * pw(x / 2) % 1000000009LL;
}
int main() {
  long long n, cr, w, k, x;
  scanf("%I64d%I64d%I64d", &n, &cr, &k);
  w = n - cr;
  long long rs = 0;
  if (cr * k > (k - 1) * n) {
    n -= w * k;
    rs = w * (k - 1) + (n % k);
    x = n / k;
    rs += k * (pw(x) + pw(x) - 2) % 1000000009LL;
    printf("%I64d\n", rs % 1000000009LL);
  } else {
    printf("%I64d\n", cr);
  }
}
