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