#include <bits/stdc++.h>
using namespace std;
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << name << " : " << arg1 << '\n';
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
const long long maxn = (long long)1e6 + 6;
const long double EPS = 1e-9;
const long long INF = (long long)1e18 + 18;
const long long mod = (long long)1e9 + 9;
long long n, m, k;
inline long long add(long long x, long long y) {
  x += y;
  if (x >= mod) x -= mod;
  return x;
}
inline long long sub(long long x, long long y) {
  x -= y;
  if (x < 0) x += mod;
  return x;
}
inline long long mul(long long x, long long y) { return (x * 1LL * y) % mod; }
inline long long binpow(long long a, long long b) {
  long long x = 1 % mod;
  while (b) {
    if (b & 1) x = mul(x, a);
    a = mul(a, a);
    b >>= 1;
  }
  return x;
}
inline long long inv(long long a) { return binpow(a, mod - 2); }
bool works(long long x) {
  long long t = x * k + ((n - x * k) / k) * (k - 1) + (n - x * k) % k;
  return t >= m;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m >> k;
  long long left = 0, right = (n + k - 1) / k;
  while (left < right) {
    long long mid = (left + right) >> 1;
    if (works(mid)) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  long long ans = binpow(2, left + 1);
  ans = sub(ans, 2);
  ans = mul(ans, k);
  ans = add(ans, sub(m, left * k));
  cout << ans << '\n';
  return 0;
}
