#include <bits/stdc++.h>
using namespace std;
long long n, m, k;
long long mypow(long long a, long long b) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % 1000000009;
    a = a * a % 1000000009;
    b /= 2;
  }
  return ans;
}
int main() {
  cin >> n >> m >> k;
  int l = n - m;
  if ((k - 1) * l >= m)
    cout << m << endl;
  else {
    long long d = m - (k - 1) * l;
    long long lev = d / k;
    d = d % k;
    long long ans = (mypow(2, lev + 1) + 1000000009 - 2) % 1000000009;
    ans = ans * k % 1000000009;
    ans = (ans + d) % 1000000009;
    ans = (ans + (k - 1) * l) % 1000000009;
    cout << ans << endl;
  }
  return 0;
}
