#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 9;
vector<long long> mult(const vector<long long> &mat,
                       const vector<long long> &vec) {
  return {(mat[0] * vec[0] + mat[1] * vec[1]) % MOD,
          (mat[2] * vec[0] + mat[3] * vec[1]) % MOD};
}
vector<long long> sqr(const vector<long long> &a) {
  return {(a[0] * a[0] + a[1] * a[2]) % MOD, (a[1] * (a[0] + a[3])) % MOD,
          (a[2] * (a[0] + a[3])) % MOD, (a[3] * a[3] + a[1] * a[2]) % MOD};
}
long long n, m, k;
long long ans(long long diff) {
  vector<long long> ans = {0, (2 * k) % MOD};
  vector<long long> mat = {2, 1, 0, 1};
  while (diff > 0) {
    if (diff % 2) ans = mult(mat, ans);
    mat = sqr(mat);
    diff /= 2;
  }
  return ans[0];
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m >> k;
  long long sub = n / k;
  if (n - sub >= m) {
    cout << m << '\n';
    return 0;
  }
  long long diff = m - (n - sub);
  long long out = ans(diff);
  out += (m - k * diff) % MOD;
  if (out < 0) out += MOD;
  out %= MOD;
  cout << out << '\n';
  return 0;
}
