#include <bits/stdc++.h>
using namespace std;
long long Bin(long long x, long long t) {
  long long Res = 1;
  while (t) {
    if (t % 2 == 1) Res = (Res * x) % 1000000009;
    x = (x * x) % 1000000009;
    t /= 2;
  }
  return Res;
}
int main() {
  long long n, m, k;
  cin >> n >> m >> k;
  long long s = n / k;
  long long t = (k - 1) * s + (n % k);
  if (t >= m) {
    cout << m << endl;
    return 0;
  }
  long long d = m - t;
  assert(d <= s);
  long long ans = 1;
  ans = Bin(2, d);
  ans = (ans - 1LL + 1000000009) % 1000000009;
  ans = (ans * 2LL * k) % 1000000009;
  ans = (ans + ((s - d) * (k - 1)) % 1000000009) % 1000000009;
  ans = (ans + n % k) % 1000000009;
  cout << ans << endl;
  return 0;
}
