#include <bits/stdc++.h>
using namespace std;
void deba(int* a, int n) {
  cerr << "| ";
  for (int i = 0; i < (n); i++) cerr << a[i] << " ";
  cerr << "|" << endl;
}
inline bool EQ(double a, double b) { return fabs(a - b) < 1e-9; }
const int INF = 1 << 30;
int MOD = 1000000009;
int main() {
  long long n, m, k;
  cin >> n >> m >> k;
  long long medz = n - m;
  n -= medz * (k);
  if (n <= 0) {
    cout << m << endl;
    return 0;
  }
  long long out = medz * (k - 1);
  long long s = n / k;
  out += n % k;
  s++;
  long long sout = 1;
  while (s > 25) {
    sout <<= 25;
    sout %= MOD;
    s -= 25;
  }
  for (int i = 0; i < (s); i++) {
    sout <<= 1;
    sout %= MOD;
  }
  if (sout == 0)
    sout = MOD - 1;
  else
    sout--;
  if (sout == 0)
    sout = MOD - 1;
  else
    sout--;
  out += (k * sout) % MOD;
  out %= MOD;
  cout << out << endl;
  return 0;
}
