#include <bits/stdc++.h>
using namespace std;
static const int MAXN = 1e6 + 10;
static const int MOD = 1e9 + 9;
int a[MAXN], b[MAXN];
int ans;
int main() {
  int n;
  scanf("%d", &n);
  n /= 2;
  a[0] = b[1] = 1;
  for (int i = 1; i <= n; i++) a[i] = a[i - 1] * 2 % MOD;
  for (int i = 2; i <= n; i++) b[i] = 1ll * b[i - 1] * (a[i] - 3 + MOD) % MOD;
  for (int i = 2; i <= n; i++) ans = (4ll * b[i] + ans) % MOD;
  ans = (2ll * ans * ans % MOD + 8ll * ans % MOD + 10) % MOD;
  printf("%d\n", ans);
  return 0;
}
