#include <bits/stdc++.h>   using namespace std;   const long long mod = 1000000009;   const int maxn = 1000010;   long long p[maxn], q[maxn];   int main() {     int i, n;     long long nAns = 0;     cin >> n;     n /= 2;     p[1] = 2;     q[1] = 1;     for (i = 2; i <= n; i++) {       p[i] = p[i - 1] * 2 % mod;       q[i] = q[i - 1] * (p[i] - 3) % mod;       nAns = (nAns + q[i] * 4) % mod;     }     cout << (2 * nAns * nAns % mod + nAns * 8 % mod + 10) % mod << endl;     return 0;   }   