#include <bits/stdc++.h>
const int N = 1000100;
const int MOD = 1000000009;
long long dp[N];
int main() {
  int n;
  scanf("%d", &n);
  long long ans = 2;
  if (n >= 4) {
    int t = (n - 4) / 2;
    long long pw = 1;
    dp[0] = 1;
    for (int i = 1; i <= t; i++) {
      dp[i] = (dp[i - 1] + pw * 4LL) % MOD;
      pw = (pw * 2LL) % MOD;
    }
  }
  long long prod = 1;
  for (int i = 2; i <= (n / 2); i++) {
    ans = (ans + prod * dp[i - 2] * 4LL) % MOD;
    prod *= dp[i - 2];
    prod %= MOD;
  }
  printf("%lld\n", (ans * ans * 2LL + 2LL) % MOD);
}
