#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1.0);
const double EPS = 1e-9;
const double INF = 2e10;
const long long OO = (1LL << 60);
int dx[] = {1, -1, 0, 0, 1, 1, -1, -1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
long long mod = 1000000009;
long long m = 1000 * 1000 * 1000 + 9;
long long calculatePower(long long power) {
  if (power == 0) {
    return 1;
  }
  long long p = calculatePower(power / 2) % mod;
  if (power % 2 == 0)
    return (p * p) % mod;
  else
    return (2LL * p * p) % mod;
}
long long bp(long long x, long long e) {
  long long y = 1;
  for (; e; e >>= 1) {
    if (e & 1) y = x * y % m;
    x = x * x % m;
  }
  return y;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL), cout.tie(NULL);
  ios::sync_with_stdio(false), cin.tie(0);
  long long n, m, k;
  cin >> n >> m >> k;
  long long num = n / k;
  long long rem = n % k;
  m -= rem;
  n -= rem;
  long long g = max(m - num * (k - 1), 0LL);
  long long r = m - g * k + rem;
  if (g > 0) {
    long long ans = ((k % mod) * (calculatePower(g + 1) - 2) + mod + r) % mod;
    cout << ans << endl;
  } else {
    cout << r << endl;
  }
  return 0;
}
