#include <bits/stdc++.h>
using namespace std;
long long int modulo = 1000000009;
long long int mida = 1000000;
int main() {
  vector<long long int> a(mida);
  vector<long long int> s(mida);
  vector<long long int> e(mida + 2);
  vector<long long int> prod(mida);
  e[0] = 1;
  for (int i = 1; i < mida + 2; i++) e[i] = (e[i - 1] * 2) % modulo;
  for (int i = 0; i < mida; i++) s[i] = (e[i + 2] - 3) % modulo;
  prod[0] = 1;
  for (int i = 1; i < mida; i++) prod[i] = (prod[i - 1] * s[i]) % modulo;
  a[1] = 2;
  for (int i = 2; i < mida; i++)
    a[i] = (a[i - 1] + (4 * prod[i - 2]) % modulo) % modulo;
  int n;
  cin >> n;
  n = n / 2;
  long long int r = (2 * (1 + (a[n] * a[n]) % modulo)) % modulo;
  cout << r << endl;
}
