#include <bits/stdc++.h>
using namespace std;
template <typename tp>
inline void read(tp& x) {
  x = 0;
  char tmp;
  bool key = 0;
  for (tmp = getchar(); !isdigit(tmp); tmp = getchar()) key = (tmp == '-');
  for (; isdigit(tmp); tmp = getchar()) x = (x << 3) + (x << 1) + (tmp ^ '0');
  if (key) x = -x;
}
const int N = 1000010, MOD = (int)(1e9 + 9);
int a[N], b[N], n;
int main() {
  read(n);
  n >>= 1;
  if (n == 1) return puts("10"), 0;
  a[2] = 1;
  for (int i = 3; i <= n; ++i) a[i] = (3 + 2 * a[i - 1]) % MOD;
  b[n] = (1 + 4ll * a[n]) % MOD;
  for (int i = n - 1; i >= 2; --i)
    b[i] = (1ll + 3ll * a[i] + 1ll * b[i + 1] * a[i]) % MOD;
  b[1] = (2ll + 2ll * b[2] + 1ll * b[2] * b[2]) % MOD;
  printf("%d\n", 2 * b[1] % MOD);
  return 0;
}
