#include <bits/stdc++.h>
#pragma warning(disable : 4996)
#pragma comment(linker, "/STACK:666000000")
using namespace std;
const int inf = (1 << 30) - 1;
const long double eps = 1e-9;
const long double pi = fabs(atan2(0.0, -1.0));
void ML(const bool v) {
  if (v) return;
  int *ass;
  for (;;) {
    ass = new int[2500000];
    for (int i = 0; i < 2500000; i++) ass[i] = rand();
  }
}
void TL(const bool v) {
  if (v) return;
  int *ass;
  ass = new int[250];
  for (;;) {
    for (int i = 0; i < 250; i++) ass[i] = rand();
  }
}
void PE(const bool v) {
  if (v) return;
  puts("ass 1 2 3 4 5 6 fuck");
  exit(0);
}
long long n, m, k;
void LoAd() { cin >> n >> m >> k; }
const long long MOD = 1000000009;
long long powmod(const long long a, const long long q) {
  if (0 == q) return 1;
  if (1 == q % 2)
    return a * powmod(a, q - 1) % MOD;
  else {
    long long tmp = powmod(a, q / 2);
    return ((tmp) * (tmp)) % MOD;
  }
}
void SoLvE() {
  if (n - m >= n / k) {
    cout << m;
  } else {
    long long canToK = (n / k * (k - 1)) + (n % k);
    long long q = m - canToK;
    long long lt = powmod(2, q + 1);
    lt -= 2;
    if (lt < 0) lt += MOD;
    lt = lt * k % MOD;
    lt = (lt + (canToK - (k - 1) * q)) % MOD;
    cout << lt;
  }
}
int main() {
  srand((int)time(NULL));
  LoAd();
  SoLvE();
  return 0;
}
