#include <bits/stdc++.h>
using namespace std;
long long n, m, k, l, r, s, t;
long long modpow(long long x, long long y) {
  if (y == 0) return 1 % 1000000009;
  long long u = modpow(x, y / 2);
  u = u * u % 1000000009;
  if (y % 2) u = u * x % 1000000009;
  return u;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m >> k;
  l = (n / k) * (k - 1) + n % k;
  r = m - l;
  if (r <= 0) {
    cout << m << endl;
    return 0;
  }
  s = m - r * (k);
  if (s <= 0) s = 0;
  t = modpow(2, r + 1);
  t = (t + 1000000009 - 2) % 1000000009;
  t = t * k % 1000000009;
  s = s + t;
  cout << s % 1000000009 << endl;
  return 0;
}
