#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long mod = 1000000009;
  long long n, m, k, out = 0, ind = 0;
  long long add = 1;
  cin >> n >> m >> k;
  int res = n - m;
  if ((res * k) >= n) {
    cout << m;
    return 0;
  }
  out = m - (n - (k * res));
  n -= (k * res);
  long long c = n / k;
  out += n % k;
  out %= mod;
  n -= n % k;
  ind = c / 56;
  c = (c % 56) + 1;
  for (int i = 0; i < ind; i++) {
    add *= ((long long)pow(2, 56)) % mod;
    add %= mod;
  }
  add = (add * ((long long)pow(2, c) % mod)) - 2;
  add %= mod;
  add = (add * k) % mod;
  out += add;
  out %= mod;
  cout << out;
  return 0;
}
