func_code_string: #include <bits/stdc++.h>   using namespace std;   const int MOD = 1000000009;   const int N = 100005;   const double PI = 4 * atan(1);   const long long MAX = 9223372036854775807;   int dx[] = {1, -1, 0, 0, 1, -1, 1, -1};   int dy[] = {0, 0, 1, -1, 1, 1, -1, -1};   long long gcd(long long a, long long b) { return (b == 0 ? a : gcd(b, a % b)); }   long long lcm(long long a, long long b) { return a * (b / gcd(a, b)); }   bool issquare(long long w) { return trunc(sqrt(w)) * trunc(sqrt(w)) == w; }   bool isprime(long long u) {     for (long long i = 2; i <= (int)sqrt(u); i++) {       if (u % i == 0) return 0;     }     return 1;   }   long long mod(long long to_mod) {     to_mod %= MOD;     while (to_mod < 0) to_mod += MOD;     return to_mod % MOD;   }   long long moduloMultiplication(long long a, long long b, long long mod) {     long long res = 0;     a %= mod;     while (b) {       if (b & 1) res = (res + a) % mod;       a = (2 * a) % mod;       b >>= 1;     }     return res;   }   long long power(long long x, long long y, long long p) {     long long res = 1;     x = x % p;     while (y > 0) {       ;       if (y & 1) res = (res * x) % p;       y = y >> 1;       x = (x * x) % p;     }     return res;   }   long long n, m, x, y, res, t, k, ans = 0, b, q, z, a, l;   int main() {     ios::sync_with_stdio(0);     cin >> n >> m >> k;     res = n / k;     ans = n % k;     m -= ans;     a = res * (k - 1);     if (a >= m) {       ans += m;       ans = mod(ans);       cout << ans;       return 0;     }     b = m - a;     y = (power(2, b + 1, MOD) - 2);     ans += moduloMultiplication(y, k, MOD);     ans = mod(ans);     ans += moduloMultiplication(k - 1, res - b, MOD);     ans = mod(ans);     cout << ans << endl;     return 0;   }   