#include <bits/stdc++.h>
using namespace std;
int arr[100001];
int gcd(int a, int b) { return (b == 0 ? a : gcd(b, a % b)); }
long long int mod = 1000000009;
int lcm(int a, int b) { return ((a * b) / gcd(a, b)); }
long long int pw(long long int b, long long int p) {
  if (!p) return 1;
  long long int sq = pw(b, p / 2);
  sq = (sq * sq) % mod;
  if (p % 2) sq = (sq * b) % mod;
  return sq;
}
long long int num;
long long int cnt;
string a[2], b[2];
map<int, int> mp;
int f(int n) {
  long long int cnt = 0;
  for (int i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      if (mp[i])
        cnt--;
      else
        cnt++;
      n /= i;
    }
  }
  if (n > 1 && mp[n])
    cnt--;
  else if (n > 1)
    cnt++;
  return cnt;
}
int d[100000];
int main() {
  long long int a, b, c;
  cin >> a >> b >> c;
  long long int st = 0, end = 10000000000, mid = 0;
  while (st < end) {
    mid = st + (end - st) / 2;
    if (mid * c > b ||
        (a - (mid * c)) / c * (c - 1) + (a - (mid * c)) % c >= b - mid * c) {
      end = mid;
    } else {
      st = mid + 1;
    }
  }
  long long int o = ((pw(2, st + 1) - 2 + mod) * c) % mod;
  cout << (o + b - st * c) % mod;
}
