#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 9;
long long quick_mod(long long a, long long b) {
  long long mul = 1;
  while (b) {
    if (b & 1) mul = mul * a % MOD;
    a = a * a % MOD;
    b >>= 1;
  }
  return mul;
}
int main() {
  long long n, m, k;
  while (~scanf("%lld %lld %lld", &n, &m, &k)) {
    long long wa = n - m;
    long long can = n / k;
    if (can <= wa)
      printf("%lld\n", m % MOD);
    else {
      long long ant = can - wa;
      long long ans = (quick_mod(2, ant) * k - k) * 2 % MOD;
      ans += m - ant * k;
      printf("%lld\n", ans % MOD);
    }
  }
  return 0;
}
