#include <bits/stdc++.h>
using namespace std;
const long long int mod = 1000000009;
long long int n, m, k;
long long int bigmod(long long int a, long long int b, long long int mod) {
  if (b == 0) return 1LL;
  long long int x = bigmod(a, b / 2, mod);
  x = (x * x) % mod;
  if (b % 2 == 1) x = (x * a) % mod;
  return x;
}
int ok(long long int x) {
  long long int v = m - x * (k - 1);
  if (v >= 0) return 1;
  return 0;
}
long long int bin() {
  long long int lo, hi, mid, ans, s;
  lo = 0;
  hi = n - m;
  ans = -1;
  while (lo <= hi) {
    mid = lo + (hi - lo) / 2;
    if (ok(mid) == 1) {
      ans = max(ans, mid);
      lo = mid + 1;
    } else
      hi = mid - 1;
  }
  return ans;
}
int main() {
  cin >> n >> m >> k;
  long long int baki, s, l = bin();
  baki = m - l * (k - 1);
  s = ((((bigmod(2, baki / k + 1, mod) - 2) % mod + mod) % mod) * k) % mod;
  baki = m - (baki / k) * k;
  s = (s + baki) % mod;
  cout << s << '\n';
  return 0;
}
