#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000009;
long long modexp_recursion(long long a, long long b, long long n) {
  long long t = 1;
  if (b == 0) return 1;
  if (b == 1) return a % n;
  t = modexp_recursion(a, b >> 1, n);
  t = t * t % n;
  if (b & 0x1) {
    t = t * a % n;
  }
  return t;
}
int main() {
  long long n, m, k;
  cin >> n >> m >> k;
  long long a = m / (k - 1);
  if (a <= n - m)
    cout << m << endl;
  else {
    long long ret = 0;
    a = n - (n - m) * k;
    long long b = a / k;
    if (b > 0) {
      ret = 2 * k * modexp_recursion(2, b, MOD) - 2 * k;
      ret = ret % MOD;
    }
    ret = (ret + (n - m) * (k - 1)) % MOD;
    ret = (ret + (a - a / k * k)) % MOD;
    cout << ret << endl;
  }
  return 0;
}
