#include <bits/stdc++.h>
using namespace std;
long long pw(long long a, long long b) {
  long long t = 1;
  if (b == 0) return t;
  if (b % 2) {
    t = t * a;
  }
  t %= 1000000009;
  long long x = pw(a, b / 2);
  x = x * x;
  x %= 1000000009;
  t *= x;
  t %= 1000000009;
  return t;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long ti = 1;
  for (long long io = 0; io < ti; io++) {
    long long n, m, k;
    cin >> n >> m >> k;
    long long oc = 0, rm;
    oc = n / k;
    rm = n % k;
    long long ans = 0;
    if (m > (n - oc)) {
      long long x = m - n + oc;
      long long y;
      y = k;
      y = y * ((pw(2, x + 1) - 2) % 1000000009);
      y %= 1000000009;
      ans += y;
      y = k - 1;
      y *= (oc - x);
      y %= 1000000009;
      ans += y;
      ans += rm;
    } else {
      ans = m;
    }
    ans %= 1000000009;
    ans += 1000000009;
    ans %= 1000000009;
    cout << ans << endl;
  }
  return 0;
}
