#include <bits/stdc++.h>
using namespace std;
const int long long Mod = 1e9 + 9;
long long power(long long a, long long b, long long m) {
  long long r = 1;
  while (b) {
    if (b & 1LL) r = r * a % m;
    b >>= 1LL;
    a = a * a % m;
  }
  return r;
}
int main() {
  long long n, m, k;
  cin >> n >> m >> k;
  long long r = n - n / k * k;
  if ((k - 1) * (n / k) + r >= m)
    cout << m << endl;
  else {
    long long t = (k - 1) * (n / k) + r;
    long long ans = power(2, m - t + 1, Mod) * k % Mod - (2 * k % Mod) +
                    (t - (m - t) * (k - 1));
    ans %= Mod;
    ans += Mod;
    ans %= Mod;
    cout << ans << endl;
  }
  return 0;
}
