#include <bits/stdc++.h>
using namespace std;
const int fin = 0, maxn = 1000010;
const int MC = 1000000009;
int g[maxn];
int main() {
  if (fin) {
    freopen("t.in", "r", stdin);
    freopen("t.out", "w", stdout);
  }
  int n, r, f, i;
  cin >> n, n /= 2;
  if (n == 1) return puts("10"), 0;
  r = MC + 1 >> 1, f = 0;
  for (g[1] = 4, i = 2; i < n; ++i) g[i] = (2 + g[i - 1] << 1) % MC;
  for (i = n - 2; i; --i) f = (long long)(f + 4) * (g[i] + 1) % MC;
  f = (f + 4) % MC;
  cout << ((long long)f * (f + 4) + 5) * 2 % MC;
  return 0;
}
