#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000009;
long long poww(long long n, long long k) {
  if (k == 0) return 1;
  if (k & 1) return (poww(n, k - 1) * n) % MOD;
  long long b = poww(n, k >> 1);
  return b * b % MOD;
}
int main() {
  long long n, m;
  int k;
  cin >> n >> m >> k;
  if ((n / k) * (k - 1) + n % k >= m) {
    cout << m;
    return 0;
  }
  int mm = 0;
  int t = m - (n / k) * (k - 1) - n % k;
  long long ans = (poww(2, t + 1) - 2) * k;
  ans += m - t * k;
  ans += MOD;
  ans %= MOD;
  cout << ans;
  return 0;
}
