func_code_string: #include <bits/stdc++.h>   using namespace std;   long long mod = 1000000009;   int n, m, k;   class Mat {    public:     long long e[2][2];     Mat mul(Mat u) {       Mat s;       for (int i = 0; i < 2; i++) {         for (int j = 0; j < 2; j++) {           s.e[i][j] = 0;           for (int k = 0; k < 2; k++) {             s.e[i][j] += e[i][k] * u.e[k][j];             s.e[i][j] %= mod;           }         }       }       return s;     }     Mat powMat(Mat u, int k) {       Mat mat;       memset(mat.e, 0, sizeof(mat.e));       mat.e[0][0] = 1;       mat.e[1][1] = 1;       while (k) {         if (k & 1) {           mat = mat.mul(u);         }         u = u.mul(u);         k = (k >> 1);       }       return mat;     }   };   bool good(int mid) {     int n1 = n - mid * k;     int m1 = m - mid * k;     int ans = n1 / k * (k - 1) + n1 % k;     if (ans >= m1) return true;     return false;   }   int main() {     scanf( %d%d%d , &n, &m, &k);     int l = 0, r = m / k;     int mid;     while (l < r) {       mid = (l + r) / 2;       if (good(mid))         r = mid;       else         l = mid + 1;     }     Mat u;     u.e[0][0] = (long long)k;     u.e[0][1] = 1L;     u.e[1][0] = 0;     u.e[1][1] = 0;     Mat v;     v.e[0][0] = 2L;     v.e[0][1] = 0;     v.e[1][0] = (long long)k;     v.e[1][1] = 1L;     u = u.mul(v.powMat(v, l));     long long ans = (u.e[0][0] - k + (m - l * k) + mod) % mod;     cout << ans;     return 0;   }   