#include <bits/stdc++.h>
using namespace std;
int n, m, i;
long long f[1000010];
const int inf = 1000000009;
int main() {
  cin >> n;
  n = n / 2;
  f[2] = 0;
  for (i = 3; i <= n; i++) f[i] = (2 * (f[i - 1] + 2)) % inf;
  for (i = n; i >= 3; i--) f[i] = f[i] = (f[i + 1] + 4) * (f[i] + 1) % inf;
  f[2] = f[3] + 4;
  if (n == 1) f[2] = 0;
  cout << 2 * ((f[2] + 2) * (f[2] + 2) + 1) % inf;
  cin >> n;
  return 0;
}
