#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000003, mod = 1000000009;
int Plus(int x, int y) { return (x += y) >= mod ? x - mod : x; }
void Pluseq(int &x, int y) {
  if ((x += y) >= mod) x -= mod;
}
int Minus(int x, int y) { return Plus(x, mod - y); }
void Minuseq(int &x, int y) { Pluseq(x, mod - y); }
int mul(long long x, int y) { return x * y % mod; }
int sqr(int x) { return mul(x, x); }
void muleq(int &x, int y) { x = mul(x, y); }
int n, p2[maxn];
int f(int i) {
  if (i >= n) return 0;
  if (i == 0) return Plus(f(i + 1), 1);
  if (i == 1) return sqr(Plus(f(i + 1), 2));
  if (i == n - 1) return 2;
  if (i >= 2 && i % 2 == 0) return Plus(f(i + 1), 2);
  return Plus(mul(f(i + 1), Minus(p2[(i + 1) / 2 + 1], 3)), 2);
}
int main() {
  scanf("%d", &n);
  p2[0] = 1;
  for (int i = 1; i <= n; i++) p2[i] = Plus(p2[i - 1], p2[i - 1]);
  printf("%d\n", mul(f(0), 2));
  return 0;
}
