#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000009;
long long bigMod(long long a, long long b) {
  if (b == 0) return 1;
  long long x = bigMod(a, b / 2);
  x = (x * x) % mod;
  if (b & 1) x = (x * a) % mod;
  return x;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  long long n, m, k;
  cin >> n >> m >> k;
  long long incorr, noDouble, noDoublePoints, leftCorr, ans, twoPow,
      kMultiplier;
  incorr = n - m;
  noDouble = min(incorr, m / (k - 1));
  noDoublePoints = (k - 1) * noDouble;
  leftCorr = m - noDoublePoints;
  ans = noDoublePoints + (leftCorr % k);
  twoPow = leftCorr / k;
  long long doubledAns = 0;
  kMultiplier = bigMod(2, twoPow + 1);
  if (kMultiplier > 1)
    kMultiplier -= 2;
  else if (kMultiplier > 0)
    kMultiplier = mod - 1;
  else
    kMultiplier = mod - 2;
  doubledAns = (k * kMultiplier) % mod;
  cout << (ans + doubledAns) % mod << "\n";
  return 0;
}
