#include <bits/stdc++.h>
using namespace std;
struct Modint {
  int val;
  Modint(int nval = 0) { val = nval; }
  Modint& operator+=(Modint r) {
    val = (val + r.val) % 1000000009;
    return *this;
  }
  Modint& operator-=(Modint r) {
    val = (val + 1000000009 - r.val) % 1000000009;
    return *this;
  }
  Modint& operator*=(Modint r) {
    val = 1LL * val * r.val % 1000000009;
    return *this;
  }
  Modint operator+(Modint r) { return Modint(*this) += r; }
  Modint operator-(Modint r) { return Modint(*this) -= r; }
  Modint operator*(Modint r) { return Modint(*this) *= r; }
};
int main() {
  vector<Modint> branchdp(1000000, 1);
  for (int i = 1; i < 1000000; i++) branchdp[i] = branchdp[i - 1] * 2 + 2 + 1;
  int n;
  cin >> n;
  Modint result = 2;
  Modint branch = 1;
  for (int i = 2; i < n;) {
    branch *= branchdp[i / 2 - 1];
    result += branch * 2;
    i++;
    result += branch * 2;
    i++;
  }
  result = result * result + 1;
  result *= 2;
  cout << result.val << '\n';
  return 0;
}
