#include <bits/stdc++.h>
using namespace std;
long long int powerLL(long long int x, long long int n) {
  long long int result = 1;
  while (n) {
    if (n & 1) result = result * x % int(1e9 + 9);
    n = n / 2;
    x = x * x % int(1e9 + 9);
  }
  return result;
}
long long int power1(long long int x, long long int m) {
  if (m == 0) return 1;
  if (m == 1) return x % int(1e9 + 9);
  long long int res = power1(x, m / 2 % int(1e9 + 9));
  if (m % 2 == 1)
    return ((res % int(1e9 + 9) * res % int(1e9 + 9)) % int(1e9 + 9) *
            (x % int(1e9 + 9))) %
           int(1e9 + 9);
  else
    return ((res % int(1e9 + 9) * res % int(1e9 + 9)) % int(1e9 + 9));
}
int main() {
  long long int n, m, k;
  cin >> n >> m >> k;
  long long int no = n / k;
  long long int filled = no * (k - 1) + n % k;
  if (filled >= m) {
    cout << m << endl;
    return 0;
  }
  long long int rem = n % k;
  m -= filled;
  long long int x = m;
  long long int filledrightnow = m * k;
  cout << ((long long int)(((power1(2, x + 1) - 2 + int(1e9 + 9))) * k) %
               int(1e9 + 9) +
           ((no - m) * (k - 1) + n % k) % int(1e9 + 9)) %
              int(1e9 + 9)
       << endl;
}
