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