#include <bits/stdc++.h>
using namespace std;
long long int mod = 1e9 + 9;
long long int pwr(long long int x) {
  if (x == 0)
    return 1;
  else if (x % 2 == 0) {
    long long int tmp = pwr(x / 2);
    return ((tmp % mod) * (tmp % mod));
  } else {
    long long int tmp = pwr(x / 2);
    return ((tmp % mod) * (tmp % mod) * 2);
  }
}
int main() {
  long long int n, m, k;
  cin >> n >> m >> k;
  long long int free = n - m;
  if ((m - (free + 1) * (k - 1)) <= 0)
    cout << m << endl;
  else {
    m = m - (free * (k - 1));
    long long int q = m / k, r = m % k;
    long long int ans = 0, p1, p2;
    p1 = (((2 * k) % mod) * ((pwr(q) + mod - 1) % mod)) % mod;
    p2 = r;
    ans = (((p1 + p2) % mod) + ((free * (k - 1)) % mod)) % mod;
    cout << ans << endl;
  }
  return 0;
}
