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