func_code_string: #include <bits/stdc++.h>   using namespace std;   const long long MOD = 1000000009;   long long pow(long long a, long long b, long long m) {     long long ans = 1;     while (b) {       if (b & 1) ans = (ans * a) % m;       b /= 2;       a = (a * a) % m;     }     return ans;   }   int32_t main() {     ios_base::sync_with_stdio(0);     cin.tie(0);     cout.tie(0);     ;     long long n, m, k;     cin >> n >> m >> k;     long long start = 0;     long long end = n;     long long ans = 1e12;     while (start <= end) {       long long middle = start + (end - start) / 2;       long long spaceLeft = n - middle * k;       long long questionsLeft = m - middle * k;       long long questionsCanBeFitted = spaceLeft / k * (k - 1) + spaceLeft % k;       if (questionsCanBeFitted >= questionsLeft) {         end = middle - 1;         ans = (k * (pow(2, middle + 1, MOD) - 2 + MOD) % MOD + (m - middle * k)) %               MOD;       } else         start = middle + 1;     }     cout << ans % MOD << endl;     return 0;   }   