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