#include <bits/stdc++.h>
using namespace std;
int N, M, K;
long long ans;
int main() {
  int i;
  long long s, e, m, t = 0, v, sum;
  cin >> N >> M >> K;
  s = 0, e = M;
  while (s <= e) {
    m = (s + e) >> 1;
    sum = K * m;
    long long space = N - K * m;
    sum += (space / K) * (K - 1) + space % K;
    if (sum >= M)
      e = m - 1, t = m;
    else
      s = m + 1;
  }
  t++;
  v = 2;
  ans = 1;
  for (i = 0; i < 60; i++, v = v * v % 1000000009)
    if ((t >> i) & 1) ans = (ans * v) % 1000000009;
  ans = (ans - 2 + 1000000009) % 1000000009 * K % 1000000009;
  ans = (ans + M - K * (t - 1)) % 1000000009;
  cout << ans << endl;
}
