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