#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000009LL;
long long f(int n) {
  long long h = 2, o = 1, p = 1, g = h, d = 4;
  for (int i = 1; i <= n; ++i) {
    const long long no = (p * o) % MOD;
    const long long nh = (4 * p * o) % MOD;
    const long long np = (p + d) % MOD;
    const long long ng = (g + nh) % MOD;
    const long long nd = (2 * d) % MOD;
    o = no, h = nh, p = np, g = ng, d = nd;
  }
  return g;
}
long long GetAnswer(int n) {
  const long long path = f((n - 2) / 2);
  const long long res = (2 * (path * path) % MOD + 2) % MOD;
  return ((res % MOD) + MOD) % MOD;
}
int main() {
  int n;
  scanf("%d", &n);
  printf("%lld\n", GetAnswer(n));
  return 0;
}
