#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000009;
vector<long long> vec;
long long powmod(long long a, long long m) {
  long long ret = 1 % MOD;
  for (; m; m >>= 1) {
    if (m & 1) {
      ret *= a;
      if (ret >= MOD) ret %= MOD;
    }
    a *= a;
    if (a >= MOD) a %= MOD;
  }
  return ret;
}
int main() {
  long long n, m, k;
  vec.clear();
  cin >> n >> m >> k;
  m = n - m;
  if (m >= n) {
    cout << '0' << endl;
    return 0;
  }
  long long p = (long long)(n / k);
  if (m >= p) {
    cout << n - m << endl;
    return 0;
  }
  long long pos = n - m * k;
  long long div = pos / k;
  long long mod = pos % k;
  long long mul = (powmod(2, div) - 1) * k % MOD * 2 % MOD;
  mul = (mul + MOD) % MOD;
  mul = (mul + mod) % MOD;
  long long ans = (mul + n - pos - m) % MOD;
  ans = (ans + MOD) % MOD;
  cout << ans << endl;
  return 0;
}
