#include <bits/stdc++.h>
using namespace std;
long long const MOD = 1000000009;
inline long long mod_add(long long x, long long y) { return (x + y) % MOD; }
inline long long mod_sub(long long x, long long y) {
  return (x - y + MOD) % MOD;
}
inline long long mod_mult(long long x, long long y) { return (x * y) % MOD; }
long long mod_pow(long long x, long long y) {
  long long ret = 1;
  while (y) {
    if (y & 1) {
      ret = mod_mult(ret, x);
    }
    x = mod_mult(x, x);
    y >>= 1;
  }
  return ret;
}
int main() {
  long long n, m, k;
  while (cin >> n >> m >> k) {
    long long total = n / k, doubled = max(total - (n - m), 0LL),
              s1 = mod_mult(mod_mult(2, k), mod_sub(mod_pow(2, doubled), 1)),
              s2 = mod_mult(mod_sub(k, 1), mod_sub(total, doubled)),
              s3 = mod_sub(n % k, (n - m) - (total - doubled));
    cout << mod_add(s1, mod_add(s2, s3)) << endl;
  }
  return 0;
}
