#include <bits/stdc++.h>
using namespace std;
int d4[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
template <class T>
void keep_max(T& a, const T& b) {
  if (a < b) a = b;
}
template <class T>
void keep_min(T& a, const T& b) {
  if (a > b) a = b;
}
template <class T>
void usort(vector<T>& a) {
  sort((a).begin(), (a).end());
  a.erase(unique((a).begin(), (a).end()));
}
const int mod = 1000000009;
long long f[500000];
void init_f(int n) {
  if (n <= 0) return;
  f[0] = 1;
  f[1] = 5;
  long long g = 2;
  for (int i = 2; i <= n; ++i) {
    f[i] = (f[i - 1] + g * 4) % mod;
    g = g * 2 % mod;
  };
}
int main() {
  int n;
  cin >> n;
  init_f(n - 2 >> 1);
  long long c = 2;
  for (int i = n - 1; i >= 3; --i) {
    if (i & 1) {
      c += 2;
    } else {
      c = c * f[i - 2 >> 1] % mod + 2;
    };
    ;
  }
  if (n > 2) {
    c += 2;
  }
  c %= mod;
  long long ans = (c * c + 1) % mod * 2 % mod;
  cout << ans;
  return 0;
}
