#include <bits/stdc++.h>
using namespace std;
long long mod_pow(long long a, long long b) {
  long long ret = 1;
  while (b) {
    if (b & 1) ret = ret * a % 1000000009;
    a = a * a % 1000000009;
    b >>= 1;
  }
  return ret;
}
int main() {
  ios::sync_with_stdio(0);
  long long n, m, k;
  cin >> n >> m >> k;
  long long y = ((n - m) * k > n ? 0 : (n - (n - m) * k) / k), ans;
  if (y == 0)
    ans = m;
  else {
    ans = k * (mod_pow(2, y + 1) - 2) % 1000000009 + m - y * k % 1000000009;
    ans %= 1000000009;
    if (ans < 0) ans += 1000000009;
  }
  cout << ans << endl;
  return 0;
}
