#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000000;
const int INF = 0x3f3f3f3f;
const int MOD = 1000000009;
template <class T>
void Read(T &x) {
  x = 0;
  char c = getchar();
  bool flag = 0;
  while (c < '0' || '9' < c) {
    if (c == '-') flag = 1;
    c = getchar();
  }
  while ('0' <= c && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  if (flag) x = -x;
}
int n;
int dp[MAXN + 10];
int main() {
  Read(n);
  n = n / 2;
  int ans = 0, t = 1;
  dp[1] = 1;
  for (int i = 2; i <= n; ++i) {
    ans = (ans + 4ll * t) % MOD;
    dp[i] = (dp[i - 1] * 2 + 3) % MOD;
    t = 1ll * t * dp[i] % MOD;
  }
  printf("%d\n", 2 * (1ll * ans * ans % MOD + 4ll * ans % MOD + 5) % MOD);
}
