#include <bits/stdc++.h>
using namespace std;
const long long M = 1000000009;
long long i, j, k, l, m, n, o, p, A, N, ans, B, t;
inline long long fastmi(long long x, long long m) {
  long long ans = 1;
  while (m) {
    if (m & 1) ans = (ans * x) % M;
    x = (x * x) % M;
    m >>= 1;
  }
  return ans;
}
int main() {
  cin >> n >> m >> k;
  N = (n - m);
  A = min(m, N * (k - 1));
  B = m - A;
  t = B / k;
  o = B - t * k;
  if (t >= 1) {
    ans = fastmi(2, t);
    ans = (ans - 1 + M) % M;
  } else
    ans = 0;
  ans = ((ans * 2) % M * k) % M;
  ans = (ans + o) % M;
  ans = (ans + A) % M;
  cout << ans << endl;
  return 0;
}
