#include <bits/stdc++.h>
using namespace std;
const long long ost = 1000000009;
long long n, m, k, res = 0;
long long invol(long long a, long long degree) {
  long long res = 1, x = a, k = degree;
  while (k != 0) {
    if (k % 2 == 1) res = res * x % ost;
    k = k / 2;
    x = x * x % ost;
  }
  return res;
}
int main(void) {
  scanf("%I64d %I64d %I64d", &n, &m, &k);
  long long m1 = n - m;
  if (n / k <= m1) {
    res = m;
  } else {
    res = 2 * (invol(2, n / k - m1) - 1) * k % ost;
    res += m - k * (n / k - m1);
    res %= ost;
  }
  printf("%I64d\n", res);
  return 0;
}
