func_code_string: #include <bits/stdc++.h>   using namespace std;   const int MOD = 1000 * 1000 * 1000 + 9;   const int MAX_N = 1000 * 1000 + 10;   long long dp1[MAX_N];   int main() {     int n;     scanf( %d , &n);     n /= 2;     if (n == 1) {       printf( %d n , 10);       return 0;     }     dp1[1] = 5;     for (int i = 2; i <= n - 2; i++) dp1[i] = (3 + 2 * dp1[i - 1]) % MOD;     long long dp2 = 1;     for (int i = 0; i < (n - 2); i++)       dp2 = (1 + dp1[n - 2 - i] * (3 + dp2)) % MOD;     dp2 += 5;     dp2 = 1 + dp2 * dp2;     dp2 *= 2;     dp2 %= MOD;     printf( %d n , (int)dp2);     return 0;   }   