#include <bits/stdc++.h>
long long mod = 1e9 + 9;
using namespace std;
long long fastpow(long long x, long long y) {
  if (y == 0) return 1;
  if (y == 1) return x;
  if (x == 0) return 0;
  long long p = fastpow(x, y / 2) % mod;
  p = (p * p) % mod;
  return (y % 2 == 0) ? p : (x * p) % mod;
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  ;
  long long n, m, k;
  cin >> n >> m >> k;
  long long doub = n / k - (n - m);
  if (doub <= 0) return cout << m, 0;
  long long res = fastpow(2, doub + 1);
  res -= 2;
  res %= mod;
  res += mod;
  res %= mod;
  res *= k;
  res %= mod;
  res += m - k * doub;
  res %= mod;
  cout << res;
  return 0;
}
