#include <bits/stdc++.h>
using namespace std;
long long n, m, k, ans;
const long long MOD = 1000000009;
long long power(long long b, long long e) {
  long long ret = 1;
  while (e) {
    if (e & 1) ret = (ret * b) % MOD;
    b = (b * b) % MOD;
    e >>= 1;
  }
  return ret;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m >> k;
  long long temp = min(n - m, n / k);
  long long temp2 = n - temp * k;
  long long v = temp2 / k;
  long long a = m - v * k;
  ans = (((power(2, v + 1) - 2 + MOD) * k) % MOD + a) % MOD;
  cout << ans << endl;
  return 0;
}
