#include <bits/stdc++.h>
using namespace std;
int n, m, k;
long long ans;
const int MOD = 1000000009;
long long powmod(long long a, int b) {
  long long ret;
  if (b == 0) {
    ret = 1;
    return ret;
  }
  ret = powmod(a, b / 2);
  ret = (ret * ret) % MOD;
  if (b % 2 == 1) ret = (ret * a) % MOD;
  return ret;
}
int main() {
  cin >> n >> m >> k;
  int d = n / k;
  int r = n - d * k;
  int num = r + d * (k - 1);
  ans = m;
  if (m > num) {
    int b = m - num;
    ans -= b * k;
    long long cnt = (powmod(2, b + 1) - 2 + MOD) % MOD;
    ans = (ans + (cnt * k) % MOD) % MOD;
  }
  cout << ans % MOD << endl;
  return 0;
}
