#include <bits/stdc++.h>
int n, m, k, c[101], mo = 1000000009;
long long t1, t2, t3, l, s, t, ans;
int main() {
  scanf("%d%d%d", &n, &m, &k);
  t1 = 0;
  t2 = m / k;
  while (t1 < t2) {
    t3 = (t1 + t2) / 2;
    l = n - t3 * k;
    s = l / k;
    t = t3 * k + s * (k - 1) + l - s * k;
    if (t < m)
      t1 = t3 + 1;
    else
      t2 = t3;
  }
  t2 = t1;
  l = 0;
  while (t1 > 0) c[++l] = t1 % 2, t1 /= 2;
  s = 1;
  while (l > 0) {
    s = s * s % mo;
    if (c[l]) s = s * 2 % mo;
    --l;
  }
  s = (s * 2 - 2 + mo) % mo;
  ans = (s * k + m - t2 * k) % mo;
  std::cout << ans << std::endl;
}
