#include <bits/stdc++.h>
using namespace std;
const int inf = 1 << 28;
const int mod = (int)1e9 + 9;
const double eps = 1e-8;
const double pi = acos(-1.0);
long long n, m, k;
long long quick(long long a, long long b) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % mod;
    b >>= 1;
    a = a * a % mod;
  }
  return ans % mod;
}
int main() {
  while (cin >> n >> m >> k) {
    long long t = m / (k - 1);
    if (m % (k - 1)) t++;
    if (t - 1 <= n - m) {
      cout << m << endl;
    } else {
      long long ans = 0;
      long long x = n - (n - m) * k;
      ans += (n - m) * (k - 1) % mod;
      ans = (ans + x % k) % mod;
      ans += quick(2, x / k + 1) * k % mod;
      ans = (ans - 2 * k) % mod;
      if (ans < 0) ans += mod;
      cout << ans << endl;
    }
  }
  return 0;
}
