#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
const long long N = 2e5 + 23;
long long n, m, k, x, ans;
long long fpow(int b) {
  long long res = 1, a = 2;
  while (b > 0) {
    if (b & 1) (res *= a) %= 1000000009;
    (a *= a) %= 1000000009;
    b >>= 1;
  }
  return res;
}
void solve() {
  cin >> n >> m >> k;
  x = max(0LL, m - ((n - n % k) / k * (k - 1) + n % k));
  ans = (((fpow(x + 1) - 2 + 1000000009) % 1000000009 * k) % 1000000009 +
         (m - (x * k) % 1000000009 + 1000000009) % 1000000009) %
        1000000009;
  cout << ans << "\n";
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(nullptr);
  solve();
  return 0;
}
