#include <bits/stdc++.h>
const int mo = 1e9 + 9;
int n, m, k;
long long power(long long a, long long b) {
  long long ans = 1;
  for (; b; b >>= 1, a = a * a % mo)
    if (b & 1) ans = ans * a % mo;
  return ans;
}
int main() {
  scanf("%d%d%d", &n, &m, &k);
  if (m <= n - n / k)
    printf("%d\n", m % mo);
  else {
    int t = m - (n - n / k);
    printf(
        "%d\n",
        int(((power(2, t) + mo - 1) % mo * k % mo * 2 % mo + m - t * k) % mo));
  }
}
