#include <bits/stdc++.h>
using namespace std;
long long mod = 1000000009;
int n, m, k;
class Mat {
 public:
  long long e[2][2];
  Mat mul(Mat u) {
    Mat s;
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        s.e[i][j] = 0;
        for (int k = 0; k < 2; k++) {
          s.e[i][j] += e[i][k] * u.e[k][j];
          s.e[i][j] %= mod;
        }
      }
    }
    return s;
  }
  Mat powMat(Mat u, int k) {
    Mat mat;
    memset(mat.e, 0, sizeof(mat.e));
    mat.e[0][0] = 1;
    mat.e[1][1] = 1;
    while (k) {
      if (k & 1) {
        mat = mat.mul(u);
      }
      u = u.mul(u);
      k = (k >> 1);
    }
    return mat;
  }
};
bool good(int mid) {
  int n1 = n - mid * k;
  int m1 = m - mid * k;
  int ans = n1 / k * (k - 1) + n1 % k;
  if (ans >= m1) return true;
  return false;
}
int main() {
  scanf("%d%d%d", &n, &m, &k);
  int l = 0, r = m / k;
  int mid;
  while (l < r) {
    mid = (l + r) / 2;
    if (good(mid))
      r = mid;
    else
      l = mid + 1;
  }
  Mat u;
  u.e[0][0] = (long long)k;
  u.e[0][1] = 1L;
  u.e[1][0] = 0;
  u.e[1][1] = 0;
  Mat v;
  v.e[0][0] = 2L;
  v.e[0][1] = 0;
  v.e[1][0] = (long long)k;
  v.e[1][1] = 1L;
  u = u.mul(v.powMat(v, l));
  long long ans = (u.e[0][0] - k + (m - l * k) + mod) % mod;
  cout << ans;
  return 0;
}
