#include <bits/stdc++.h>
using namespace std;
long long int modpow(long long int x, long long int n) {
  if (n == 0) return 1 % 1000000009;
  long long int u = modpow(x, n / 2);
  u = (u * u) % 1000000009;
  if (n % 2 == 1) u = (u * x) % 1000000009;
  return u;
}
int main() {
  long long int n, m, k;
  cin >> n >> m >> k;
  if (n - m >= ((m + k - 2) / (k - 1)) - 1)
    cout << m << "\n";
  else {
    long long int a = m - (n - m) * (k - 1),
                  ans = (n - m) * (k - 1) % 1000000009;
    ans += a % k;
    a /= k;
    ans = (ans + (((2 * k) % 1000000009) * ((modpow(2, a) - 1) % 1000000009)) %
                     1000000009) %
          1000000009;
    cout << ans << "\n";
  }
}
