#include <bits/stdc++.h>
using namespace std;
const int M = 1e9 + 9;
int n, m, k, a, b, c;
long long ans;
long long modpow(long long z, long long x) {
  long long ret = 1;
  for (; x; x >>= 1) {
    if (x & 1) ret = ret * z % M;
    z = z * z % M;
  }
  return ret;
}
int main() {
  scanf("%d %d %d", &n, &m, &k);
  a = (n / k) * (k - 1);
  a += n % k;
  if (a >= m) {
    return !printf("%d\n", m);
  }
  b = m - a;
  ans += modpow(2, b) - 1;
  ans %= M;
  ans *= k;
  ans %= M;
  ans *= 2;
  ans %= M;
  c = a - (k - 1) * b;
  ans += c;
  ans %= M;
  printf("%lld\n", ans);
  return 0;
}
