#include <bits/stdc++.h>
using namespace std;
long long bm(long long base, int power, int modu) {
  if (power == 0) {
    return 1;
  }
  if (power % 2 == 0) {
    long long ret = (bm(base, power / 2, modu));
    return (ret * ret) % modu;
  } else {
    return (base * (bm(base, power - 1, modu))) % modu;
  }
}
int main() {
  long long n, m, k;
  cin >> n >> m >> k;
  long long puron = 0;
  long long hole = n / k;
  puron += n % k;
  puron += hole * (k - 1);
  if (puron >= m) {
    cout << m << "\n";
    return 0;
  }
  long long notun_p = 0;
  notun_p = (m - puron);
  long long ans = (puron - (notun_p * (k - 1)) + 1000000009) % 1000000009;
  long long temp = (k * 2) % 1000000009;
  long long temp2 =
      (bm(2, (notun_p), 1000000009) - 1 + 1000000009) % 1000000009;
  temp = (temp * temp2) % 1000000009;
  cout << (ans + temp) % 1000000009 << "\n";
  return 0;
}
