#include <bits/stdc++.h>
using namespace std;
long long n, m, k;
long long bin(long long x, long long a) {
  long long y = 1;
  while (a) {
    if (a & 1) y *= x, y %= 1000000009ll;
    x *= x, x %= 1000000009ll;
    a >>= 1;
  }
  return y;
}
int main() {
  cin >> n >> m >> k;
  long long t = n / k, r = n % k, ans = 0;
  long long a = m - r - (k - 1) * t;
  if (a <= 0) a = 0;
  ans = (bin(2, a + 1) + 1000000009ll - 2) % 1000000009ll;
  ans = (ans * k) % 1000000009ll;
  ans = (ans + m - k * a) % 1000000009ll;
  cout << ans << "\n";
  return 0;
}
