func_code_string: #include <bits/stdc++.h>   using namespace std;   template <typename Arg1>   void __f(const char* name, Arg1&& arg1) {     cerr << name <<   :   << arg1 <<   n ;   }   template <typename Arg1, typename... Args>   void __f(const char* names, Arg1&& arg1, Args&&... args) {     const char* comma = strchr(names + 1,  , );     cerr.write(names, comma - names) <<   :   << arg1 <<   |  ;     __f(comma + 1, args...);   }   const long long maxn = (long long)1e6 + 6;   const long double EPS = 1e-9;   const long long INF = (long long)1e18 + 18;   const long long mod = (long long)1e9 + 9;   long long n, m, k;   inline long long add(long long x, long long y) {     x += y;     if (x >= mod) x -= mod;     return x;   }   inline long long sub(long long x, long long y) {     x -= y;     if (x < 0) x += mod;     return x;   }   inline long long mul(long long x, long long y) { return (x * 1LL * y) % mod; }   inline long long binpow(long long a, long long b) {     long long x = 1 % mod;     while (b) {       if (b & 1) x = mul(x, a);       a = mul(a, a);       b >>= 1;     }     return x;   }   inline long long inv(long long a) { return binpow(a, mod - 2); }   bool works(long long x) {     long long t = x * k + ((n - x * k) / k) * (k - 1) + (n - x * k) % k;     return t >= m;   }   signed main() {     ios_base::sync_with_stdio(false);     cin.tie(0);     cout.tie(0);     cin >> n >> m >> k;     long long left = 0, right = (n + k - 1) / k;     while (left < right) {       long long mid = (left + right) >> 1;       if (works(mid)) {         right = mid;       } else {         left = mid + 1;       }     }     long long ans = binpow(2, left + 1);     ans = sub(ans, 2);     ans = mul(ans, k);     ans = add(ans, sub(m, left * k));     cout << ans <<   n ;     return 0;   }   