#include <bits/stdc++.h>
int main() {
  long long i, n, m, k, ll = 1000000009, pow = 2;
  scanf("%lld%lld%lld", &n, &m, &k);
  if ((n - m) >= n / k)
    printf("%lld", m);
  else {
    long long count = 1, t1 = (n / k) - (n - m), t;
    t = t1 + 1;
    while (t > 0) {
      if (t % 2) count = count * pow % ll;
      pow = pow * pow % ll;
      t /= 2;
    }
    count = (count + ll - 2) % ll * k % ll;
    count = (count + m - k * t1) % ll;
    printf("%lld", count);
  }
}
