#include <bits/stdc++.h>
int pw2(int k) {
  int mul = 2;
  int res = 1;
  while (k > 0) {
    if (k % 2) res = (1ll * mul * res) % 1000000009;
    mul = (1ll * mul * mul) % 1000000009;
    k /= 2;
  }
  return res;
}
int k, n, m;
int main() {
  scanf("%d %d %d", &n, &m, &k);
  if (1ll * (n - m + 1) * (k - 1) >= 1ll * m) {
    printf("%d ", m);
    return 0;
  }
  int curr = (n - m + 1) * (k - 1);
  int res = m - (n - m + 1) * (k - 1);
  int group;
  if (res % k == 0)
    group = res / k;
  else {
    group = (res / k + 1);
    curr = (n - m) * (k - 1) + (res % k - 1);
  }
  int ans = ((pw2(group) - 1) * 2) % 1000000009;
  ans = (1ll * ans * k) % 1000000009;
  ans = (ans + curr) % 1000000009;
  printf("%d", ans);
}
