#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000009;
int fastMin(int x, int y) { return (((y - x) >> (32 - 1)) & (x ^ y)) ^ x; }
int fastMax(int x, int y) { return (((y - x) >> (32 - 1)) & (x ^ y)) ^ y; }
template <class T>
long long mod_pow(T a, T n, T mod) {
  long long ret = 1;
  long long p = a % mod;
  while (n) {
    if (n & 1) ret = ret * p % mod;
    p = p * p % mod;
    n >>= 1;
  }
  return ret;
}
int main() {
  long long n, m, k;
  cin >> n >> m >> k;
  long long a = min((n - m) * k, n);
  long long b = n - a;
  long long block = b / k;
  long long x = ((mod_pow<long long>(2, block + 1, MOD) - 2) % MOD + MOD) % MOD;
  x = x * k % MOD;
  x = x + (b - block * k);
  x += a - (n - m);
  x %= MOD;
  cout << x << endl;
}
