#include <bits/stdc++.h>
using namespace std;
constexpr long long mod = 1000000009;
template <typename T, size_t N, size_t M>
struct matrix {
  T at[N][M];
};
template <typename T, size_t A, size_t B, size_t C>
matrix<T, A, C> operator*(matrix<T, A, B> const& p, matrix<T, B, C> const& q) {
  matrix<T, A, C> r = {};
  for (int y = (0); (y) < (A); ++(y)) {
    for (int z = (0); (z) < (B); ++(z)) {
      for (int x = (0); (x) < (C); ++(x)) {
        r.at[y][x] += p.at[y][z] * q.at[z][x];
        r.at[y][x] %= mod;
      }
    }
  }
  return r;
}
template <typename T, size_t A, size_t B>
array<T, A> operator*(matrix<T, A, B> const& p, array<T, B> const& q) {
  array<T, A> r = {};
  for (int y = (0); (y) < (A); ++(y)) {
    for (int z = (0); (z) < (B); ++(z)) {
      r[y] += p.at[y][z] * q[z];
      r[y] %= mod;
    }
  }
  return r;
}
int main() {
  long long n, m, k;
  cin >> n >> m >> k;
  long long x = n - m;
  long long l = n - x * k;
  if (l <= 0) {
    cout << m << endl;
  } else {
    long long y = 0;
    matrix<long long, 3, 3> f = {{{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}};
    matrix<long long, 3, 3> e = {{{2, 0, 2 * k}, {0, 1, 0}, {0, 0, 1}}};
    for (int i = 0; (1ll << i) <= (l / k); ++i) {
      if ((1ll << i) & (l / k)) {
        f = f * e;
      }
      e = e * e;
    }
    array<long long, 3> v{{0, 0, 1}};
    y += (f * v)[0];
    y %= mod;
    y += l % k;
    y %= mod;
    y += x * (k - 1);
    y %= mod;
    cout << y << endl;
  }
  return 0;
}
