#include <bits/stdc++.h>
using namespace std;
long long PowMod(long long a, long long b) {
  if (b == 0) return 1LL;
  if (b % 2 == 1) {
    long long t = PowMod(a, (b - 1) / 2);
    t = (t * t) % 1000000009;
    return (a * t) % 1000000009;
  } else {
    long long t = PowMod(a, b / 2);
    return (t * t) % 1000000009;
  }
}
int main() {
  long long n, m, k;
  cin >> n >> m >> k;
  long long p = (n / k);
  if (m <= (p * (k - 1) + (n % k))) {
    cout << m << endl;
  } else {
    long long rem = m - (p * (k - 1) + (n % k));
    long long ans = m - (rem * k);
    long long fact = PowMod(2, rem);
    fact = (fact - 1 + 1000000009) % 1000000009;
    fact = (fact * 2) % 1000000009;
    fact = (fact * k) % 1000000009;
    ans = (ans + fact) % 1000000009;
    cout << ans % 1000000009 << endl;
  }
  return 0;
}
