#include <bits/stdc++.h>
using namespace std;
long long int power(long long int a, long long int b) {
  if (b == 1) return a;
  if (b % 2 == 0) {
    long long int temp = power(a, b / 2);
    return (temp * temp) % 1000000009;
  } else
    return (a * power(a, b - 1)) % 1000000009;
}
int main() {
  long long int n, m, k;
  scanf("%lld %lld %lld", &n, &m, &k);
  long long int g = (n + k - 1) / k, com = n / k, ex = n % k;
  long long int lim = com * (k - 1) + ex;
  if (m <= lim)
    printf("%lld\n", m);
  else {
    long long int var = m - lim;
    long long int res = ((2 * k * (power(2, var) - 1)) % 1000000009 +
                         ((k - 1) * (com - var)) % 1000000009 + ex) %
                        1000000009;
    printf("%lld\n", (res + 1000000009) % 1000000009);
  }
  return 0;
}
