#include <bits/stdc++.h>   using namespace std;   long long bigpow(long long x, long long n) {     if (n == 0) return 1;     long long temp = bigpow(x, n / 2);     return n % 2 == 0 ? (temp * temp) % 1000000009                       : (x * ((temp * temp) % 1000000009)) % 1000000009;   }   int main() {     long long n, m, k, x, t, p, q, gaps, groups;     cin >> n >> m >> k;     gaps = n - m;     groups = m % (k - 1) == 0 ? m / (k - 1) : m / (k - 1) + 1;     if (gaps >= groups - 1)       cout << m << endl;     else {       x = n - gaps * k;       t = 2 * (bigpow(2, x / k) - 1) * k + x % k;       t += gaps * (k - 1);       cout << t % 1000000009 << endl;     }     return 0;   }   