#include <bits/stdc++.h>
using namespace std;
long long x, now, N, M, K;
long long pow(long long A, long long K) {
  long long ans = 1ll;
  while (K) {
    if (K & 1) ans = (long long)ans * A % 1000000009;
    A = (long long)A * A % 1000000009;
    K >>= 1;
  }
  return ans % 1000000009;
}
int main() {
  cin >> N >> M >> K;
  if (M == 0) {
    cout << 0 << endl;
    return 0;
  }
  if ((K - 1) * (N - M + 1) + N - M >= N) {
    cout << M % 1000000009 << endl;
    return 0;
  }
  x = 0;
  now = N - (N - M) * K;
  x = (pow(2ll, now / K) * x % 1000000009 +
       (pow(2ll, now / K + 1) - 2 + 1000000009) * K % 1000000009 + now % K) %
      1000000009;
  x += (N - M) * (K - 1) % 1000000009;
  x %= 1000000009;
  cout << x % 1000000009 << endl;
}
