#include <bits/stdc++.h>
using namespace std;
int pfix(int x) { return x >= 1000000009 ? x - 1000000009 : x; }
int dfix(int x) { return x < 0 ? x + 1000000009 : x; }
int ti[1000005];
int fi[1000005];
int main() {
  int n;
  scanf("%d", &n);
  int dans = min(6, (n - 1) * 2);
  int btopn = (n - 4) >> 1;
  register int f = 1;
  register int t = 4;
  for (int i = 1; i <= btopn; ++i) {
    t = pfix(t << 1);
    f = 1LL * f * dfix(t - 3) % 1000000009;
    dans = (dans + 1LL * f * 4) % 1000000009;
  }
  printf("%lld\n", (2LL * dans * dans + 2) % 1000000009);
}
