#include <bits/stdc++.h>
using namespace std;
void setup() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout.precision(15);
}
const long long MOD = 1e9 + 9;
long long N, M, K;
long long mod_pow(long long b, long long e) {
  if (e == 0) return 1;
  if (e & 1) return b * mod_pow(b, e - 1) % MOD;
  return mod_pow(b * b % MOD, e / 2);
}
int main() {
  setup();
  cin >> N >> M >> K;
  long long W = N - M;
  long long F = N - W * K;
  long long D = (F < K) ? 0 : (F / K);
  long long R = M - D * K;
  long long A = (mod_pow(2, D) - 1 + MOD) % MOD;
  A = (A * 2 * K) % MOD;
  A = (A + R) % MOD;
  cout << A << endl;
}
