#include <bits/stdc++.h>
using namespace std;
const unsigned long long MOD = 1e9 + 9;
const int INF = 1e9;
const unsigned long long INF64 = 9e18;
const long double EPS = 1e-12;
const long double PI = 3.14159265358979310000;
const unsigned long long MD = 535355424;
const unsigned long long T = 25342;
const int N = 200001;
const int M = 201;
unsigned long long n, m, k;
unsigned long long step(unsigned long long first, unsigned long long second) {
  if (second == 0) return 1LL;
  unsigned long long s = step(first, second / 2LL);
  if (second & 1LL)
    return ((((s) * (s)) % MOD) * first) % MOD;
  else
    return (((s) * (s)) % MOD);
}
bool get(unsigned long long first) {
  unsigned long long s = first * k;
  unsigned long long q = m - s;
  s += (q / (k - 1LL)) * k;
  if (q % (k - 1LL) == 0)
    s--;
  else
    s += q % (k - 1LL);
  return s <= n;
}
void solve(unsigned long long first) {
  unsigned long long s = first * k;
  unsigned long long q = m - s;
  cout << (((((step(2LL, first + 1LL) + MOD - 2LL) % MOD) * k) % MOD) + q) %
              MOD;
}
int main() {
  cin >> n >> m >> k;
  unsigned long long l = 0, r = m / k;
  while (r - l > 1) {
    unsigned long long mid = (l + r) / 2;
    if (get(mid))
      r = mid;
    else
      l = mid;
  }
  if (get(l))
    solve(l);
  else
    solve(r);
  return 0;
}
