#include <bits/stdc++.h>   using namespace std;   long long i, n, now, ans, hh, m, p = 1000000009;   int main() {     scanf( %lld , &n);     if (n == 2) {       puts( 10 );       return 0;     }     m = n / 2;     now = 4;     hh = 1;     for (i = 3; i <= m; i++) {       now = now * 2 % p;       hh = hh * (now - 3) % p;       ans = (ans + hh) % p;     }     ans = ans * 4 + 6;     ans %= p;     ans = ans * ans % p;     ans++;     ans = ans * 2 % p;     printf( %lld , ans);   }   