#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
long long pov(int a, int n) {
  if (n == 0) return 1LL;
  long long half = pov(a, n / 2);
  half = half * half % 1000000009;
  if (n % 2) half = half * a % 1000000009;
  return half;
}
long long n, m, k;
int main() {
  cin >> n >> m >> k;
  long long v = (n / k) * (k - 1) + n % k;
  if (v >= m) {
    cout << m << endl;
  } else {
    long long diff = m - v;
    long long res = pov(2, diff + 1) - 2 % 1000000009;
    res += 1000000009;
    res = res * k % 1000000009;
    res += m - diff * k;
    cout << res % 1000000009 << endl;
  }
  return 0;
}
