#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int64_t rnd(int64_t l = 0, int64_t r = INT_MAX) {
  return uniform_int_distribution<int64_t>(l, r)(rng);
}
bool in_range(int64_t x, int64_t l, int64_t r) { return l <= x && x <= r; }
template <typename H, typename... T>
void inp(H& head) {
  cin >> head;
}
template <typename H, typename... T>
void inp(H& head, T&... tail) {
  cin >> head;
  inp(tail...);
}
template <typename T>
inline istream& operator>>(istream& in, vector<T>& a) {
  for (T& x : a) in >> x;
  return in;
}
template <typename T, typename U>
inline istream& operator>>(istream& in, pair<T, U>& a) {
  in >> a.first >> a.second;
  return in;
}
template <int64_t D, typename T>
struct vec : public vector<vec<D - 1, T>> {
  static_assert(D >= 1, "Vector dimensions must be greater than zero !!");
  template <typename... Args>
  vec(int64_t n = 0, Args... args)
      : vector<vec<D - 1, T>>(n, vec<D - 1, T>(args...)) {}
};
template <typename T>
struct vec<1, T> : public vector<T> {
  vec(int64_t n = 0, T val = T()) : vector<T>(n, val) {}
};
const int64_t inf = 1e15;
const bool testcases = false;
void init_main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
}
template <typename T>
T inverse(T a, T m) {
  T u, v, t;
  u = 0;
  v = 1;
  while (a != 0) {
    t = m / a;
    m -= t * a;
    swap(a, m);
    u -= t * v;
    swap(u, v);
  }
  assert(m == 1);
  return u;
}
template <typename T>
class Modular {
 public:
  using Type = typename decay<decltype(T::value)>::type;
  constexpr Modular() : value() {}
  template <typename U>
  Modular(const U& x) {
    value = normalize(x);
  }
  template <typename U>
  static Type normalize(const U& x) {
    Type v;
    if (-mod() <= x && x < mod())
      v = static_cast<Type>(x);
    else
      v = static_cast<Type>(x % mod());
    if (v < 0) v += mod();
    return v;
  }
  const Type& operator()() const { return value; }
  template <typename U>
  explicit operator U() const {
    return static_cast<U>(value);
  }
  constexpr static Type mod() { return T::value; }
  Modular& operator+=(const Modular& other) {
    if ((value += other.value) >= mod()) value -= mod();
    return *this;
  }
  Modular& operator-=(const Modular& other) {
    if ((value -= other.value) < 0) value += mod();
    return *this;
  }
  template <typename U>
  Modular& operator+=(const U& other) {
    return *this += Modular(other);
  }
  template <typename U>
  Modular& operator-=(const U& other) {
    return *this -= Modular(other);
  }
  Modular& operator++() { return *this += 1; }
  Modular& operator--() { return *this -= 1; }
  Modular operator++(int32_t) {
    Modular result(*this);
    *this += 1;
    return result;
  }
  Modular operator--(int32_t) {
    Modular result(*this);
    *this -= 1;
    return result;
  }
  Modular operator-() const { return Modular(-value); }
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int32_t>::value,
                     Modular>::type&
  operator*=(const Modular& rhs) {
    value = normalize(static_cast<int64_t>(value) *
                      static_cast<int64_t>(rhs.value));
    return *this;
  }
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value,
                     Modular>::type&
  operator*=(const Modular& rhs) {
    int64_t q = static_cast<int64_t>(static_cast<long double>(value) *
                                     rhs.value / mod());
    value = normalize(value * rhs.value - q * mod());
    return *this;
  }
  template <typename U = T>
  typename enable_if<!is_integral<typename Modular<U>::Type>::value,
                     Modular>::type&
  operator*=(const Modular& rhs) {
    value = normalize(value * rhs.value);
    return *this;
  }
  Modular& operator/=(const Modular& other) {
    return *this *= Modular(inverse(other.value, mod()));
  }
  template <typename U>
  friend const Modular<U>& abs(const Modular<U>& v) {
    return v;
  }
  template <typename U>
  friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);
  template <typename U>
  friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);
  template <typename U>
  friend std::istream& operator>>(std::istream& stream, Modular<U>& number);

 private:
  Type value;
};
template <typename T>
bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) {
  return lhs.value == rhs.value;
}
template <typename T, typename U>
bool operator==(const Modular<T>& lhs, U rhs) {
  return lhs == Modular<T>(rhs);
}
template <typename T, typename U>
bool operator==(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) == rhs;
}
template <typename T>
bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(const Modular<T>& lhs, U rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(U lhs, const Modular<T>& rhs) {
  return !(lhs == rhs);
}
template <typename T>
bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) {
  return lhs.value < rhs.value;
}
template <typename T>
Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T, typename U>
Modular<T> operator+(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T, typename U>
Modular<T> operator+(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T>
Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T, typename U>
Modular<T> operator-(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T, typename U>
Modular<T> operator-(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T>
Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T, typename U>
Modular<T> operator*(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T, typename U>
Modular<T> operator*(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T>
Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> operator/(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> operator/(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
  assert(b >= 0);
  Modular<T> x = a, res = 1;
  U p = b;
  while (p > 0) {
    if (p & 1) res *= x;
    x *= x;
    p >>= 1;
  }
  return res;
}
template <typename T>
bool IsZero(const Modular<T>& number) {
  return number() == 0;
}
template <typename T>
string to_string(const Modular<T>& number) {
  return to_string(number());
}
template <typename T>
std::ostream& operator<<(std::ostream& stream, const Modular<T>& number) {
  return stream << number();
}
template <typename T>
std::istream& operator>>(std::istream& stream, Modular<T>& number) {
  typename common_type<typename Modular<T>::Type, int64_t>::type x;
  stream >> x;
  number.value = Modular<T>::normalize(x);
  return stream;
}
constexpr int32_t MOD = 1e9 + 9;
using Mint = Modular<std::integral_constant<decay<decltype(MOD)>::type, MOD>>;
vector<Mint> inv, inv_fact, fact;
void build_factorial(int64_t maximum = 1000000) {
  for (int64_t i = 2; i * i <= MOD; i++) assert(MOD % i);
  inv = {0, 1};
  fact = inv_fact = {1, 1};
  maximum = max(maximum, decltype(maximum)(1));
  inv.resize(maximum + 1);
  fact.resize(maximum + 1);
  inv_fact.resize(maximum + 1);
  for (int64_t i = 2; i <= maximum; i++) {
    inv[i] = inv[MOD % i] * (MOD - MOD / i);
    fact[i] = i * fact[i - 1];
    inv_fact[i] = inv[i] * inv_fact[i - 1];
  }
}
Mint choose(int64_t n, int64_t r) {
  if (in_range(r, decltype(r)(0), n))
    return fact[n] * inv_fact[r] * inv_fact[n - r];
  return 0;
}
Mint inv_choose(int64_t n, int64_t r) {
  assert(in_range(r, decltype(r)(0), n));
  return inv_fact[n] * fact[r] * fact[n - r];
}
Mint permute(int64_t n, int64_t r) {
  if (in_range(r, decltype(r)(0), n)) return fact[n] * inv_fact[n - r];
  return 0;
}
Mint inv_permute(int64_t n, int64_t r) {
  assert(in_range(r, decltype(r)(0), n));
  return inv_fact[n] * fact[n - r];
}
void solve(int64_t tc) {
  int64_t n, m, k;
  cin >> n >> m >> k;
  int64_t extra = m - ((n / k) * (k - 1) + n % k);
  if (extra <= 0) {
    cout << m << '\n';
    return;
  }
  int64_t cons = min(n, (extra + 1) * k - 1);
  int64_t X = cons / k;
  Mint scoreTillCons = power(Mint(2), X + 1) - 2;
  scoreTillCons *= k;
  scoreTillCons += (cons % k);
  Mint scoreAfterCons = m - cons;
  cout << scoreTillCons + scoreAfterCons << '\n';
}
int32_t main(int32_t argc, char** argv) {
  init_main();
  int64_t TC = 1;
  if (testcases) cin >> TC;
  for (int64_t tc = 1; tc <= TC; ++tc) {
    solve(tc);
    108;
  }
  return 0;
}
