#include <bits/stdc++.h>
using namespace std;
long long pd(long long a, long long x, long long p) {
  if (x == 0) return 1;
  long long res = pd(a, x >> 1, p);
  res *= res;
  res %= p;
  return (x & 1) ? (a * res) % p : res;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  ;
  int n, k, m;
  long long mo = 1000000000ll + 9;
  cin >> n >> m >> k;
  int cnt = n / k;
  int savegood = n - cnt;
  if (m <= savegood) {
    cout << m << "\n";
  } else {
    int nogood = m - savegood;
    long long ans = 0;
    long long X = pd(2, nogood + 1, mo);
    X = (mo + X - 2) % mo;
    ans = (1ll * k * max(1ll, X)) % mo;
    ans = (ans + (m - 1ll * nogood * k)) % mo;
    cout << ans << "\n";
  }
  cin.sync();
  cin.get();
  return 0;
}
