#include <bits/stdc++.h>
using namespace std;
long long bigpow(long long x, long long n) {
  if (n == 0) return 1;
  long long temp = bigpow(x, n / 2);
  return n % 2 == 0 ? (temp * temp) % 1000000009
                    : (x * ((temp * temp) % 1000000009)) % 1000000009;
}
int main() {
  long long n, m, k, x, t, p, q, gaps, groups;
  cin >> n >> m >> k;
  gaps = n - m;
  groups = m % (k - 1) == 0 ? m / (k - 1) : m / (k - 1) + 1;
  if (gaps >= groups - 1)
    cout << m << endl;
  else {
    x = n - gaps * k;
    t = 2 * (bigpow(2, x / k) - 1) * k + x % k;
    t += gaps * (k - 1);
    cout << t % 1000000009 << endl;
  }
  return 0;
}
