#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
  if (a < b) swap(a, b);
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long n, m, k;
long long MODULO = 1000000009LL;
struct matrix {
  long long V[2][2];
  int N, M;
  matrix() {
    memset(V, 0, sizeof V);
    N = 2;
    M = 2;
  }
  matrix(int A, int B) {
    memset(V, 0, sizeof V);
    N = A;
    M = B;
  }
  matrix operator*(matrix X) {
    matrix Z(N, X.M);
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < X.M; j++) {
        long long acum = 0;
        for (int k = 0; k < M; k++) {
          acum = (acum + (V[i][k] * X.V[k][j]) % MODULO + MODULO) % MODULO;
        }
        Z.V[i][j] = acum;
      }
    }
    return Z;
  }
  matrix operator%(long long modulo) {
    matrix Z(N, M);
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++) {
        Z.V[i][j] = V[i][j] % modulo;
      }
    }
    return Z;
  }
  void print() {
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++) {
        cout << V[i][j] << " ";
      }
      cout << endl;
    }
  }
  void clear() {
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++) {
        V[i][j] = 0;
      }
    }
  }
};
matrix I;
matrix pow(matrix F, long long q) {
  if (q == 0LL) return I;
  if (q == 1LL) return F;
  matrix result = I;
  while (q) {
    if (q & 1LL) {
      result = result * F;
      q--;
    }
    F = F * F;
    q = q / 2;
  }
  return result;
}
long long f(long long x) {
  matrix F = matrix(2, 2);
  F.V[0][0] = 2LL;
  F.V[0][1] = 2LL * k;
  F.V[1][0] = 0LL;
  F.V[1][1] = 1LL;
  matrix F2 = pow(F, x);
  return F2.V[0][1];
}
int main() {
  I.clear();
  for (int i = 0; i < 2; i++) I.V[i][i] = 1LL;
  cin >> n >> m >> k;
  long long dif = max(0LL, ((m - ((n - m + 1) * (k - 1))) + k - 1) / k);
  long long ans = (f(dif) + m - (k * dif)) % MODULO;
  cout << ans << endl;
}
