#include <bits/stdc++.h>
using namespace std;
long long n, m, k, ans, mod = 1000 * 1000 * 1000 + 9;
long long pow(long long a) {
  if (a == 0) return 1;
  long long ret = pow(a / 2);
  ret *= ret;
  if (a % 2 == 1) ret *= 2;
  ret %= mod;
  return ret;
}
int main() {
  cin >> n >> m >> k;
  long long q = n - m;
  long long f = min(n / k, q);
  if (m <= (f) * (k - 1) + n % k) {
    cout << m << endl;
    return 0;
  } else {
    long long ans = f * k - f;
    m = m - ans;
    long long q = m / k;
    ans += 2 * (pow(q) - 1) * k + m % k;
    ans %= mod;
    if (ans < 0) ans += mod;
    cout << ans << endl;
    return 0;
  }
  return 0;
}
