#include <bits/stdc++.h>
using namespace std;
long long int n, m, k;
long long int pw(long long int a, long long int b) {
  if (b < 0) return 0;
  if (b == 0) return 1;
  long long int k = pw(a, b / 2) % 1000000009;
  k = k * k;
  k %= 1000000009;
  if (b & 1) k *= a;
  return k % 1000000009;
}
void solve() {
  cin >> n >> m >> k;
  long long int sep = (n - m) * (k - 1);
  long long int tog = m - sep;
  if (tog <= 0) {
    cout << m;
    exit(0);
  }
  long long int grp = tog / k;
  long long int rem = tog % k;
  long long int anssep = sep;
  long long int anstog =
      ((k * (pw(2LL, grp + 1) + 1000000009 - 2)) % 1000000009 + rem) %
      1000000009;
  cout << (anssep + anstog) % 1000000009;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long int T = 1;
  while (T--) solve();
  return 0;
}
