#include <bits/stdc++.h>
using namespace std;
void smain();
int main() {
  ios_base::sync_with_stdio(0);
  smain();
  return 0;
}
inline long long pm(long long aa, long long nn) {
  long long res = 1;
  for (; nn; nn >>= 1, aa = aa * aa % 1000000009)
    if (nn & 1) res = res * aa % 1000000009;
  return res;
}
long long solve(long long n, long long m, long long k) {
  long long res = min(n % k, m);
  n -= res, m -= res;
  long long x = n / k;
  long long y = min(x * (k - 1), m);
  res += y;
  m -= y;
  long long t = (pm(2, m + 1) - 2) * k % 1000000009;
  if (t < 0) t += 1000000009;
  return (res + t - m * (k - 1) % 1000000009 + 1000000009) % 1000000009;
}
void smain() {
  long long n, m, k;
  for (; cin >> n >> m >> k;) {
    cout << solve(n, m, k) << '\n';
  }
}
