#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 9;
long long n, m, k, ans;
long long binpow(long long a, long long b) {
  long long ret = 1LL;
  while (b) {
    if (b & 1LL) ret *= a, ret %= mod;
    a *= a, a %= mod, b >>= 1LL;
  }
  return ret;
}
int main() {
  cin >> n >> m >> k;
  long long rm = min(n - m, m / (k - 1LL));
  ans = rm * (k - 1LL) % mod;
  rm = m - rm * (k - 1LL), ans += (rm % k);
  rm = (binpow(2LL, rm / k + 1LL) - 2LL + mod) % mod, rm = rm * k % mod;
  cout << (ans + rm) % mod << endl;
}
