#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000009;
const int MAXN = 100005;
long long modpow(long long x, long long n, long long m) {
  if (n == 0) return 1 % m;
  long long u = modpow(x, n / 2, m);
  u = (u * u) % m;
  if (n % 2 == 1) u = (u * x) % m;
  return u;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  long long ans = 2;
  long long n, m, k;
  cin >> n >> m >> k;
  long long a = n / k;
  long long b = n % k;
  if (m <= (k - 1) * a + b)
    cout << m % mod;
  else {
    long long c = m - (k - 1) * a - b;
    long long reste = (a - c) * (k - 1) + b;
    long long count;
    count = k * modpow(2, c + 1, mod) - 2 * k;
    count += mod;
    count += reste;
    count %= mod;
    cout << count;
  }
  return 0;
}
