#include <bits/stdc++.h>
using namespace std;
long long mu;
long long an;
long long powe(long long a, long long b) {
  a %= 1000000009;
  b %= 1000000009;
  mu = a;
  an = 1;
  while (b != 0) {
    if (b % 2) an = (an * mu) % 1000000009;
    mu = (mu * mu) % 1000000009;
    b /= 2;
  }
  return an;
}
int main() {
  long long n;
  long long m;
  long long k;
  cin >> n >> m >> k;
  if ((n - m) * (k - 1) >= m) {
    cout << m % 1000000009 << endl;
    return 0;
  }
  long long ans = ((n - m) * (k - 1)) % 1000000009;
  m -= (n - m) * (k - 1);
  ans = (ans + m % k) % 1000000009;
  m /= k;
  long long ans1 = 0;
  if (m) {
    ans1 += (2 * k) % 1000000009;
    ans1 = (ans1 * (powe(2, m) + 1000000009 - 1)) % 1000000009;
  }
  cout << (ans + ans1) % 1000000009 << endl;
  return 0;
}
