#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
const long long mod = 1e9 + 9;
int n;
long long pw, s, ss;
long long ans;
int main() {
  scanf("%d", &n);
  n /= 2;
  pw = 2ll;
  s = 1ll;
  ss = 0ll;
  for (int i = 2; i <= n; i++) {
    pw *= 2ll;
    if (pw >= mod) pw -= mod;
    (s *= pw - 3ll) %= mod;
    ss += s;
  }
  ss = (ss * 4ll + 1ll) % mod;
  ans = (4ll + 4ll * ss + 2ll * ss * ss) % mod;
  printf("%I64d\n", ans);
  return 0;
}
