#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2;
long long MOD = 1000000009;
long long mod = 1000000009;
struct Matrix {
  int N, a[MAXN][MAXN];
  void init() {
    fill(a[0], a[N], 0);
    a[0][0] = 2, a[0][1] = 2;
    a[1][0] = 0, a[1][1] = 1;
  }
  void mul(const Matrix r) {
    Matrix l(*this);
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        long long temp = 0;
        for (int k = 0; k < N; ++k) {
          temp += l.a[i][k] * (long long)r.a[k][j];
        }
        a[i][j] = temp % MOD;
      }
    }
  }
  void pow(long long e) {
    Matrix temp(*this);
    fill(a[0], a[MAXN], 0);
    for (int i = 0; i < N; ++i) {
      a[i][i] = 1;
    }
    for (; e; e >>= 1) {
      if (e & 1) {
        this->mul(temp);
      }
      temp.mul(temp);
    }
  }
} mat;
int main() {
  long long n, k, m;
  cin >> n >> m >> k;
  long long ans = 0;
  long long wa = n - m;
  if (wa * k >= n)
    ans = m;
  else {
    long long nn = n - wa * k;
    long long a = nn / k;
    long long b = nn % k;
    if (a == 0)
      ans = 0;
    else {
      mat.N = 2;
      mat.init();
      mat.pow(a);
      ans = (long long)mat.a[0][1];
      ans = ans * k % mod;
    }
    ans += b + wa * (k - 1) % mod;
    ans %= mod;
  }
  cout << ans << endl;
  return 0;
}
