#include <bits/stdc++.h>
using namespace std;
const int Mo = 1000000009;
long long Pow(long long x, int p) {
  long long res = 1;
  while (p) {
    if (p & 1) res = res * x % Mo;
    p >>= 1;
    x = x * x % Mo;
  }
  return res;
}
int main() {
  long long N, M, K, x, ans;
  cin >> N >> M >> K;
  if ((K - 1) * (N - M + 1) >= M) {
    ans = M;
  } else {
    x = N - K * (N - M);
    ans = (Pow(2, x / K + 1) + Mo - 2) % Mo * K % Mo;
    ans += x % K + (K - 1) * (N - M);
    ans %= Mo;
  }
  cout << ans << endl;
}
