#include <bits/stdc++.h>
using namespace std;
long long n, m, k;
long long mod(long long a) {
  return (a >= 0) ? (a % 1000000009)
                  : ((a % 1000000009) + 1000000009) % 1000000009;
}
long long mod_add(long long a, long long b) { return mod(mod(a) + mod(b)); }
long long mod_mult(long long a, long long b) { return mod(mod(a) * mod(b)); }
long long mod_pow(long long a, long long b) {
  long long ret = 1;
  while (b) {
    if (b & 1) {
      ret = mod_mult(ret, a);
    }
    a = mod_mult(a, a);
    b /= 2;
  }
  return ret;
}
int main(void) {
  cin >> n >> m >> k;
  long long ex = n % k;
  n -= ex;
  m -= ex;
  if ((k - 1) * n / k >= m) {
    cout << mod(m + ex) << "\n";
    return 0;
  }
  long long val = n / k - (n - m);
  long long ans = mod_mult(mod_pow(2, val + 1) - 2, k);
  ans = mod_add(ans, m);
  ans = mod_add(ans, -val * k);
  ans = mod_add(ans, ex);
  cout << mod(ans) << "\n";
  return 0;
}
