#include <bits/stdc++.h>   int n, m;   long long k;   long long pow(int n) {     if (n == 0) return 1;     long long tmp = pow(n >> 1);     tmp = tmp * tmp % 1000000009ll;     if (n & 1) tmp = tmp * 2ll % 1000000009ll;     return tmp;   }   int main() {     scanf( %d%d%I64d , &n, &m, &k);     int t = n - m;     long long ans = 0;     if (m == 0) {       puts( 0 );       return 0;     }     if (n - t * k < k) {       ans = m;     } else {       int num = (n - t * k) / k;       ans = (pow(num + 1) - 2 + 1000000009ll) * k % 1000000009ll;       ans = (ans + (n - t * k) % k) % 1000000009ll;       ans = (ans + t * (k - 1)) % 1000000009ll;     }     printf( %I64d n , ans);     return 0;   }   