#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000010;
const int MOD = 1000000009;
inline int getInt() {
  int ret;
  char ch;
  bool flg = false;
  while ((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-');
  ret = ch - '0';
  while ((ch = getchar()) >= '0' && ch <= '9') ret = ret * 10 + (ch - '0');
  return flg ? -ret : ret;
}
int r[MAXN], f[MAXN];
int g[MAXN];
int main() {
  int N;
  scanf("%d", &N);
  if (N == 1) {
    puts("2");
    return 0;
  }
  if (N == 2) {
    puts("10");
    return 0;
  }
  if (N == 3) {
    puts("16");
    return 0;
  }
  N -= 3;
  r[0] = 1;
  for (int i = 1; i <= N; i++) r[i] = 2 * r[i - 1] % MOD;
  f[0] = 1;
  for (int i = 1; i <= N; i++)
    f[i] = (f[i - 1] + (long long)r[i - 1] * 4 % MOD) % MOD;
  g[0] = 1;
  for (int i = 1; (i << 1) <= N; i++) g[i] = (long long)g[i - 1] * f[i] % MOD;
  int ans = 0;
  for (int i = 1; (i << 1) <= N; i++) {
    if (N - (i << 1) >= 1)
      (ans += 4LL * g[i] % MOD) %= MOD;
    else
      (ans += 2LL * g[i] % MOD) %= MOD;
  }
  ans += 6;
  ans = ((long long)ans * ans % MOD + 1) % MOD;
  cout << (ans * 2) % MOD << '\n';
}
