#include <bits/stdc++.h>
using namespace std;
long long n;
int main() {
  scanf("%I64d", &n);
  long long a = 4, b = 6, c = 4;
  if (n == 2) {
    printf("10\n");
    return 0;
  }
  for (; n > 4; n -= 2) {
    a = a * 2 % 1000000009ll;
    c = c * (a - 3ll + 1000000009ll) % 1000000009ll;
    b = (b + c) % 1000000009ll;
  }
  printf("%I64d\n",
         (2ll * b % 1000000009ll * b % 1000000009ll + 2ll % 1000000009ll) %
             1000000009ll);
}
