#include <bits/stdc++.h>
using namespace std;
const int N = 2;
const int mod = 1000000009;
int n = 2;
long long A[][2] = {2, 0, 2, 1};
struct Mat {
  long long a[N][N];
  void init() {
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++) a[i][j] = A[i][j];
  }
  void init1() {
    memset(a, 0, sizeof(a));
    for (int i = 0; i < n; i++) a[i][i] = 1;
  }
  void init2() { memset(a, 0, sizeof(a)); }
};
Mat operator*(const Mat& a, const Mat& b) {
  Mat res;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
      res.a[i][j] = 0LL;
      for (int k = 0; k < n; k++) {
        res.a[i][j] += a.a[i][k] * b.a[k][j];
      }
      res.a[i][j] %= mod;
    }
  return res;
}
Mat operator^(Mat& A, int p) {
  Mat res;
  res.init1();
  while (p) {
    if (p & 1) res = res * A;
    p >>= 1;
    if (p <= 0) break;
    A = A * A;
  }
  return res;
}
int F(int c, int k) {
  if (c == 1) return 2 * k;
  c--;
  Mat B;
  B.init();
  Mat C = B ^ c;
  long long res = 2 * k * C.a[0][0] % mod;
  res += k * C.a[1][0] % mod;
  res %= mod;
  return (int)res;
}
int gao(int n, int m, int k) {
  int w = n - m;
  long long tmp = (long long)(w + 1) * (k - 1);
  if (m <= tmp)
    return m;
  else {
    int r = m - tmp;
    int sum = r + k - 1;
    int c = sum / k;
    long long res = F(c, k) + sum % k;
    res %= mod;
    res += (long long)(w) * (k - 1);
    res %= mod;
    return (int)res;
  }
}
int main() {
  int n, m, k;
  while (~scanf("%d%d%d", &n, &m, &k)) printf("%d\n", gao(n, m, k));
  return 0;
}
