#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000009;
long long power(long long a, long long b) {
  long long res = 1;
  a %= mod;
  assert(b >= 0);
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % mod % mod;
    a = a * a % mod;
  }
  return res;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  long long i, j, k, t, n, m, p;
  cin >> n >> m >> k;
  long long re = m / (k - 1);
  long long tot = re * (k - 1) + re - 1;
  if (m % (k - 1) != 0) {
    tot = tot + m % (k - 1) + 1;
    re++;
  }
  if (tot <= n) {
    cout << m << "\n";
  } else {
    long long co = tot - n;
    long long sc = 0;
    long long lng = (co) * (k - 1);
    if (m % (k - 1) == 0) {
      lng = lng + k - 1;
    } else {
      lng = lng + m % (k - 1);
    }
    long long lef = m - lng;
    long long ct = lng / k;
    lef = lef + lng % k;
    sc = sc + k * (2 * (power(2, ct) - 1) % mod) % mod;
    sc = sc + lef;
    sc = sc % mod;
    cout << sc % mod << "\n";
  }
  return 0;
}
