#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000009;
long long po(long long X, long long p) {
  if (p == 0) return 1;
  long long res = po(X, p / 2);
  res = (res % MOD * res % MOD) % MOD;
  if (p % 2) res = (res % MOD * X % MOD) % MOD;
  return res;
}
int main() {
  long long N, M, K;
  scanf("%I64d%I64d%I64d", &N, &M, &K);
  long long ans = 0;
  if (M < K)
    ans = M;
  else {
    long long sisa = N - M;
    long long normal = min(M, (K - 1) * sisa), temp = 0;
    M -= normal;
    if (M / K > 0) {
      long long pangkat = M / K + 1;
      long long maxi = po(2, pangkat);
      maxi = ((maxi - 2) + MOD) % MOD;
      temp = (temp % MOD + (maxi % MOD * K % MOD) % MOD) % MOD;
    }
    if (M % K != 0) temp = (temp % MOD + (M % K) % MOD) % MOD;
    ans = ((ans % MOD + temp % MOD) % MOD + normal % MOD) % MOD;
  }
  printf("%I64d\n", ans);
  return 0;
}
