#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000009;
long long mypow(long long a, long long n) {
  if (n == 0) return 1;
  if (n % 2 == 0) {
    long long t = mypow(a, n / 2);
    return t * t % MOD;
  } else {
    long long t = mypow(a, n - 1);
    return a * t % MOD;
  }
}
int main() {
  int n, m, k;
  cin >> n >> m >> k;
  int can = n - m;
  int need = n / k;
  if (can >= need) {
    cout << m << endl;
  } else {
    n -= can * k;
    int steps = n / k;
    int mod = n % k;
    long long res = can * (k - 1) + mod;
    if (steps > 0) {
      res += (((mypow(2, steps + 1) - 2 + MOD) % MOD) * (long long)k) % MOD;
    }
    res %= MOD;
    cout << res << endl;
  }
  return 0;
}
