#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
const double eps = 1e-11;
const int inf = 0x3f3f3f3f;
template <class T>
void show(T a, int n) {
  for (int i = 0; i < n; ++i) cout << a[i] << ' ';
  cout << endl;
}
template <class T>
void show(T a, int r, int l) {
  for (int i = 0; i < r; ++i) show(a[i], l);
  cout << endl;
}
const int N = 1e6 + 111;
const long long mod = 1e9 + 9;
int main() {
  long long n, m, k;
  cin >> n >> m >> k;
  long long a = n - m;
  long long tp = a * k + k - 1;
  if (tp >= n) {
    cout << m << endl;
    return 0;
  }
  tp = a * k;
  long long x = n - tp;
  long long y = x / k;
  long long ans = 2 * k % mod;
  long long ans2 = (x - y * k % mod + a * (k - 1) % mod + mod) % mod;
  long long res = 1;
  long long tmp = 2;
  while (y) {
    if (y & 1) res = (res * tmp) % mod;
    tmp = (tmp * tmp) % mod;
    y >>= 1;
  }
  res = (res - 1 + mod) % mod;
  ans = (ans * res) % mod;
  cout << (ans + ans2) % mod;
  return 0;
}
