#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:16777216")
using namespace std;
const double PI = 2.0 * acos(0.0);
template <class T>
inline T MAX(T a, T b) {
  if (a > b) return a;
  return b;
}
template <class T>
inline T MIN(T a, T b) {
  if (a < b) return a;
  return b;
}
long long POW(long long x) {
  if (x == 0) return 1;
  if (x == 1) return 2;
  long long t = POW(x / 2);
  t = t * t % 1000000009;
  if (x % 2) t = t * 2 % 1000000009;
  return t;
}
int main() {
  long long n, m, k;
  cin >> n >> m >> k;
  long long tmp = (k - 1) * (n / k) + n % k;
  if (tmp >= m)
    cout << m;
  else {
    long long b = m - tmp;
    long long res = 2 * (POW(b) - 1) * k % 1000000009;
    res = (res + m - b * k) % 1000000009;
    cout << res;
  }
}
