#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000 * 1000 * 1000 + 9;
long long powe(long long x, long long p) {
  if (p == 0) return 1;
  long long y = powe(x, p / 2);
  if (p % 2) return (x * (y * y) % mod) % mod;
  return (y * y) % mod;
}
int main() {
  ios::sync_with_stdio(false);
  long long n, m, k;
  cin >> n >> m >> k;
  long long t = n - m;
  long long a = n / k;
  long long b = max(a - t, 0ll);
  long long ans = ((powe(2, b + 1) - 2) * k) % mod;
  ans = (ans + (m - b * k)) % mod;
  cout << (ans + mod) % mod << endl;
  return 0;
}
