#include <bits/stdc++.h>
using namespace std;
long long fast_exp_mod(long long x, long long a) {
  long long ans = 1, current = x;
  while (a) {
    if (a % 2 == 1) ans = (ans * current) % ((long long)(1e9) + 9);
    a /= 2;
    current = (current * current) % ((long long)(1e9) + 9);
  }
  return ans;
}
long long n, m, k;
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m >> k;
  long long singles = min(m, (n - m) * (k - 1));
  long long cont = m - singles;
  long long ans =
      (((fast_exp_mod(2, (cont / k) + 1) + ((long long)(1e9) + 9) - 2) %
        ((long long)(1e9) + 9)) *
       k) %
      ((long long)(1e9) + 9);
  ans = (ans + cont % k) % ((long long)(1e9) + 9);
  ans = (ans + singles) % ((long long)(1e9) + 9);
  cout << ans << endl;
  return 0;
}
