#include <bits/stdc++.h>
using namespace std;
long long Res[1 << 19];
long long A[1 << 19];
int main() {
  int N;
  scanf("%d", &N);
  N >>= 1;
  int i;
  A[0] = 1;
  for (i = (1); i < (N); ++i) A[i] = (3 + 2 * A[i - 1]) % 1000000009;
  Res[0] = 2;
  long long mul = A[0];
  for (i = (1); i < (N); ++i) {
    Res[i] = (Res[i - 1] + 4 * mul) % 1000000009;
    mul = mul * A[i] % 1000000009;
  }
  printf("%d\n", int((2 + 2 * Res[N - 1] * Res[N - 1]) % 1000000009));
  return 0;
};
