#include <bits/stdc++.h>   using namespace std;   int main() {     long long n = 0, ans = 0, mod = 1000000009LL;     scanf( %I64d , &n);     if (n >= 5) {       vector<long long> lev(n + 1, 0);       if (n >= 3) lev[3] = 1;       if (n >= 4) lev[4] = 1;       if (n >= 5) lev[5] = 5;       for (int i = 6; i <= n; i++)         if (i % 2 == 0)           lev[i] = 1;         else           lev[i] = (2 * lev[i - 2] + 3) % mod;       long long dob = 1;       for (int i = 5; i <= n; i++)         if (lev[i] > 1) {           dob = (dob * lev[i]) % mod;           ans = (ans + 4 * dob) % mod;         }       ans = (ans + 6) % mod;       ans = (ans * ans) % mod;       ans = (ans + mod - 4) % mod;       ans = (2 * ans) % mod;       ans = (ans + 10) % mod;       printf( %I64d n , ans);     }     if (n == 1) printf( 2 n );     if (n == 2) printf( 10 n );     if (n == 3) printf( 34 n );     if (n == 4) printf( 74 n );     return 0;   }   