#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
const int N = 1e6 + 5, M = 100 + 5, OO = 0x3f3f3f3f, MOD = 1e9 + 9;
long long n, m, k, ans, tmp, mm;
long long fp(int x, int p) {
  if (!p) return 1;
  long long y = fp(x, p >> 1) % MOD;
  y = (y * y) % MOD;
  if (p & 1) y = (y * x) % MOD;
  return y;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m >> k;
  if (n / k <= n - m)
    cout << m;
  else {
    long long sc = (n - m) * (k - 1);
    sc += (m - sc) % k;
    cout << (sc % MOD + (fp(2, (m - sc) / k + 1) + MOD - 2) % MOD * k % MOD) %
                MOD;
  }
  return 0;
}
