#include <bits/stdc++.h>
using namespace std;
template <class T>
inline int size(const T& c) {
  return c.size();
}
using namespace std;
int fastMax(int x, int y) { return (((y - x) >> (32 - 1)) & (x ^ y)) ^ y; }
int fastMin(int x, int y) { return (((y - x) >> (32 - 1)) & (x ^ y)) ^ x; }
const long long cmod = 1000000009;
long long n, m, k, s, res;
int modpow(int a, int n, int m) {
  if (n == 0) return 1;
  if (n % 2 == 1)
    return ((long long)a * modpow(a, n - 1, m)) % m;
  else {
    long long x = modpow(a, n / 2, m);
    return (x * x) % m;
  }
}
int main() {
  scanf("%d%d%d", &n, &m, &k);
  if (n - m >= n / k) {
    cout << m << endl;
    return 0;
  }
  long long s = n - m;
  long long left = n - s * k;
  long long sl = left / k;
  res = (((long long)modpow(2, sl + 1, cmod) - 2) * k) % cmod;
  res = ((res + left % k) % cmod + s * (k - 1)) % cmod;
  cout << (res % cmod + cmod) % cmod << endl;
  fclose(stdin);
  fclose(stdout);
  return 0;
}
