#include <bits/stdc++.h>
const int MOD = 1e9 + 9;
int n;
int main() {
  scanf("%d", &n), n >>= 1;
  int sum = 0;
  for (int i = 2, pow2 = 4, pro = 1; i <= n; ++i, pow2 = pow2 * 2 % MOD)
    sum = (sum + 4LL * (pro = 1LL * pro * (pow2 - 3) % MOD)) % MOD;
  printf("%lld\n", (2LL * sum * sum + 8LL * sum + 10) % MOD);
  return 0;
}
