#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1.0);
const double EPS = 1e-7;
long long kcnt(long long k, long long cnt) {
  long long res = 1, x = 2;
  cnt++;
  while (cnt) {
    if (cnt & 1) res = (res * x) % 1000000009;
    cnt >>= 1;
    x = (x * x) % 1000000009;
  }
  res -= 2;
  if (res < 0) res += 1000000009;
  res *= k;
  res %= 1000000009;
  return res;
}
int main() {
  long long n, m, k;
  cin >> m >> n >> k;
  long long N = n;
  m -= n;
  n -= (k - 1) * m;
  if (n <= 0) {
    cout << N << endl;
    return 0;
  }
  long long cnt = n / k;
  long long rest = n % k;
  long long res = kcnt(k, cnt);
  res += m * (k - 1);
  res += rest;
  res %= 1000000009;
  cout << res << endl;
}
