#include <bits/stdc++.h>
using namespace std;
const int INF = (1 << 30);
const long long MM = 1000000009;
long long qm(long long s, long long t) {
  if (t == 0) return 1;
  if (t == 1) return s;
  long long res = qm(s, t >> 1);
  res = (res * res) % MM;
  if (t & 1) res = res * s % MM;
  return res;
}
int main() {
  int n, m, k;
  scanf("%d%d%d", &n, &m, &k);
  int C = m - n / k * (k - 1) - n % k;
  long long res, tmp;
  if (C > 0) {
    tmp = (qm(2, C + 1) - 2) * k;
    tmp = (tmp % MM + MM) % MM;
    res = (tmp + m - k * C + MM) % MM;
  } else
    res = m;
  int ans = res;
  printf("%d\n", ans);
  return 0;
}
