#include <bits/stdc++.h>
using namespace std;
const int M = 1e9 + 9;
long long n;
long long sum = 1;
int main() {
  scanf("%lld", &n);
  for (long long i = 3, last = -1, P = 1; i <= n; i++) {
    if (i & 1) {
      last = (2 * last + 3) % M;
      P = (P * last) % M;
    }
    sum = (sum + P) % M;
  }
  sum = (sum << 1) % M;
  sum = (sum * sum) % M;
  sum = ((sum + 1) << 1) % M;
  printf("%lld", sum);
  return 0;
}
