func_code_string: #include <bits/stdc++.h>   using namespace std;   const long long MOD = 1000000009;   long long modexp_recursion(long long a, long long b, long long n) {     long long t = 1;     if (b == 0) return 1;     if (b == 1) return a % n;     t = modexp_recursion(a, b >> 1, n);     t = t * t % n;     if (b & 0x1) {       t = t * a % n;     }     return t;   }   int main() {     long long n, m, k;     cin >> n >> m >> k;     long long a = m / (k - 1);     if (a <= n - m)       cout << m << endl;     else {       long long ret = 0;       a = n - (n - m) * k;       long long b = a / k;       if (b > 0) {         ret = 2 * k * modexp_recursion(2, b, MOD) - 2 * k;         ret = ret % MOD;       }       ret = (ret + (n - m) * (k - 1)) % MOD;       ret = (ret + (a - a / k * k)) % MOD;       cout << ret << endl;     }     return 0;   }   