#include <bits/stdc++.h>
using namespace std;
const unsigned long long P = 239017, MaxN = 2100000, INF = 100000000;
const long long mod = 1000000009;
long long step(int t) {
  if (t == 0) return 1;
  if (t % 2 == 0) {
    long long a = step(t / 2);
    return (a * a) % mod;
  }
  return (2 * step(t - 1)) % mod;
}
int n, m, k;
int main() {
  scanf("%d%d%d", &n, &m, &k);
  int t = m - n % k - (n / k) * (k - 1);
  if (t <= 0) {
    printf("%d", m);
    return 0;
  }
  long long ans =
      (((long long)k * (step(t + 1) - 2)) % mod + m - t * k + mod) % mod;
  printf("%I64d", ans);
  return 0;
}
