#include <bits/stdc++.h>
using namespace std;
unsigned long long expo(unsigned long long base, unsigned long long power,
                        unsigned long long mod) {
  unsigned long long res = 1;
  while (power > 0) {
    if (power & 1) res = (res * base) % mod;
    power = power >> 1;
    base = (base * base) % mod;
  }
  return res;
}
signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long TESTS = 1;
  while (TESTS--) {
    long long n, m, k;
    cin >> n >> m >> k;
    long long w = n - m;
    long long x = n / k;
    if (w >= x) {
      cout << (m % 1000000009);
      return 0;
    }
    long long l = n - (w * k);
    long long q = (l / k);
    long long rem = (l % k);
    long long sum = 0;
    sum = ((expo(2, q + 1, 1000000009) - 2 + 1000000009) % 1000000009) *
          (k % 1000000009);
    sum %= 1000000009;
    sum += rem;
    sum %= 1000000009;
    sum += (w % 1000000009) * ((k - 1) % 1000000009);
    sum %= 1000000009;
    cout << sum;
  }
  return 0;
}
