#include <bits/stdc++.h>
using namespace std;
long long pwr(long long x, long long p) {
  long long ans = 1;
  while (p > 0) {
    if (p % 2 == 1) {
      ans *= x;
      ans %= 1000000009;
      --p;
    } else {
      x = x * x;
      x %= 1000000009;
      p /= 2;
    }
  }
  return ans;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  long long n, m, k;
  cin >> n >> m >> k;
  long long chk = n % k, res;
  chk += (n / k) * (k - 1);
  if (chk >= m) {
    cout << m;
    return 0;
  }
  res = chk;
  res -= (k - 1) * (m - chk);
  res += 2 * k * (pwr(2, m - chk) - 1);
  res %= 1000000009;
  cout << res;
}
