#include <bits/stdc++.h>
using namespace std;
long long power(long long q) {
  long long power = 2;
  long long x = 1;
  while (q != 0) {
    if (q % 2 == 1) {
      x = (x * power) % 1000000009;
    }
    power = (power * power) % 1000000009;
    q /= 2;
  }
  return x;
}
int main() {
  long long n, m, k;
  cin >> n >> m >> k;
  long long a = m / (k - 1);
  if (m % (k - 1) == 0) {
    if ((n - m) >= a - 1) {
      cout << m << endl;
    } else {
      a = (k - 1) * ((a - 1) - (n - m) + 1);
      long long r = a % k;
      long long q = a / k;
      long long ans = 0;
      ans = (power(q + 1) * k) % 1000000009;
      ans = ans + ((-2 * k) % 1000000009 + 1000000009);
      ans = (ans + r + (((n - m) * (k - 1)) % 1000000009)) % 1000000009;
      cout << ans << endl;
    }
  } else {
    long long tr = m % (k - 1);
    if ((n - m) >= a)
      cout << m << endl;
    else {
      a = (k - 1) * ((a - 1) - (n - m) + 1);
      a += tr;
      long long r = a % k;
      long long q = a / k;
      long long ans = 0;
      ans = (power(q + 1) * k) % 1000000009;
      ans = ans + ((-2 * k) % 1000000009 + 1000000009);
      ans %= 1000000009;
      ans = (ans + r + (((n - m) * (k - 1)) % 1000000009)) % 1000000009;
      cout << ans << endl;
    }
  }
}
