#include <bits/stdc++.h>
using namespace std;
long long powmod(long long x, long long y, long long z) {
  if (y == 1) return x;
  long long c = powmod(x, y / 2, z);
  if (y & 1)
    return (c * c) % z * x % z;
  else
    return c * c % z;
}
signed main() {
  long long n, m, k;
  cin >> n >> m >> k;
  long long x = m - (n / k) * (k - 1) - n % k;
  if (x <= 0)
    cout << m % 1000000009;
  else {
    long long y = n / k - x;
    long long z = (y * (k - 1) + n % k) % 1000000009;
    cout << (((powmod(2, x + 1, 1000000009) * k - 2 * k) % 1000000009 + z) +
             1000000009) %
                1000000009;
  }
  return 0;
}
