#include <bits/stdc++.h>
using namespace std;
int _;
const long long mod = 1000 * 1000 * 1000 + 9;
long long n, m, k;
long long Pow(long long a, long long b) {
  if (b == 0) return 1 % mod;
  long long c = Pow(a, b / 2);
  c = (c * c) % mod;
  if (b % 2) c = (c * a) % mod;
  return c;
}
long long F(long long a) {
  long long x = a / k;
  return ((((Pow(2, x + 1) - 2 + mod) % mod) * k) % mod + a % k) % mod;
}
int main() {
  cin >> n >> m >> k;
  long long x = n - m;
  if (x * k + (k - 1) >= n) {
    cout << m << endl;
    return 0;
  }
  long long num = n - x * k;
  long long add = x * (k - 1);
  cout << (F(num) + add) % mod << endl;
  return 0;
}
