#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000009;
long long powmod(long long a, long long b) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans *= a, ans %= mod;
    b >>= 1;
    a *= a, a %= mod;
  }
  return ans;
}
long long jud(long long n, long long m, long long k) {
  return m * k <= (n + 1) * (k - 1);
}
int main() {
  long long n, m, k;
  long long l, r;
  cin >> n >> m >> k;
  l = 0, r = 1000000000;
  long long mid;
  while (l < r) {
    mid = (l + r) / 2;
    if (k * mid > m || jud(n - k * mid, m - k * mid, k))
      r = mid;
    else
      l = mid + 1;
  }
  long long ans = 0;
  ans = powmod(2, l) - 1;
  ans = (ans + mod) % mod;
  ans *= 2, ans %= mod;
  ans *= k, ans %= mod;
  ans += m - l * k, ans %= mod;
  cout << ans << endl;
}
