#include <bits/stdc++.h>
using namespace std;
int modexp(int x, int e) {
  int r = 1;
  for (int i = 31 - __builtin_clz(e); i >= 0; i--) {
    r = ((long long)r * r) % 1000000009;
    if (e & 1 << i) {
      r = ((long long)r * x) % 1000000009;
    }
  }
  return r;
}
int main() {
  long long N, M, K;
  cin >> N >> M >> K;
  long long V = N - M;
  if ((V + 1) * K - 1 >= N) {
    cout << M << endl;
  } else {
    long long result = V * (K - 1);
    M -= result;
    result += K * (modexp(2, M / K + 1) + 1000000009 - 2);
    result += M % K;
    cout << result % 1000000009 << endl;
  }
  return 0;
}
