func_code_string: #include <bits/stdc++.h>   using namespace std;   const int maxn = 1e6;   const int md = 1000000009;   int n;   long long two[maxn + 5], f[maxn + 5], ans;   int main() {     two[0] = 1;     for (int i = 1; i <= maxn; ++i) two[i] = two[i - 1] * 2 % md;     scanf( %d , &n);     f[n] = 2;     for (int i = n - 1; i >= 2; --i) {       if (i & 1)         f[i] = (f[i + 1] + 2) % md;       else {         int k = i >> 1;         f[i] = (2 + ((two[k - 1] - 1 + md) % md * 4 + 1) * f[i + 1]) % md;       }     }     f[1] = (1 + f[2] * f[2]) % md;     ans = f[1] * 2 % md;     printf( %lld n , ans);     return 0;   }   