#include <bits/stdc++.h>
const long long N = 1000006;
using namespace std;
const long long MOD = 1000000009LL;
template <typename T>
T gcd(T a, T b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
template <typename T>
T power(T x, T y, long long m = MOD) {
  T ans = 1;
  while (y > 0) {
    if (y & 1LL) ans = (ans * x) % m;
    y >>= 1LL;
    x = (x * x) % m;
  }
  return ans % m;
}
int32_t main() {
  long long n, m, k;
  cin >> n >> m >> k;
  long long free = (n / k) * (k - 1) + n % k;
  if (m <= free) {
    cout << m;
    return 0;
  }
  long long rem = m - free;
  long long a = power(2LL, rem) - 1LL;
  if (a < 0) a += MOD;
  a = (a * 2LL) % MOD;
  long long ans = (k * a) % MOD;
  long long trem = free - rem * (k - 1);
  ans = (ans + trem) % MOD;
  cout << ans << '\n';
}
