#include <bits/stdc++.h>
using namespace std;
long long n, sum = 0, k = 4, t = 2;
int main() {
  scanf("%lld", &n);
  while (n -= 2) {
    t = t * 2 % 1000000009;
    k = k * (t - 3) % 1000000009;
    sum = (sum + k) % 1000000009;
  }
  sum =
      ((((2 * sum) % 1000000009) * sum) % 1000000009 + (8 * sum) % 1000000009) %
          1000000009 +
      10;
  sum %= 1000000009;
  printf("%lld", sum);
  return 0;
}
