#include <bits/stdc++.h>
using namespace std;
long long N;
long long f[1000005], dp[1000005], sum;
void end(long long x) {
  printf("%I64d\n", x);
  exit(0);
}
int main() {
  long long i, j, tx;
  scanf("%I64d", &N);
  if (N == 1) end(2);
  if (N == 2) end(10);
  f[0] = 1;
  for (i = 1; i <= N; i++) f[i] = (f[i - 1] * 2 + 3) % 1000000009;
  dp[2] = 1;
  for (i = 3; i <= N; i++)
    if (i & 1) {
      tx = (i - 3) / 2;
      if (i == N)
        dp[i] = dp[i - 1] * (i - 2) % 1000000009;
      else
        dp[i] = dp[i - 1] * f[tx] % 1000000009;
      sum = (sum + dp[i] * 2) % 1000000009;
    } else {
      dp[i] = dp[i - 1];
      sum = (sum + dp[i] * 2) % 1000000009;
    }
  end((sum * 4 % 1000000009 + sum * sum % 1000000009 + 5) % 1000000009 * 2 %
      1000000009);
  return 0;
}
