#include <bits/stdc++.h>
using namespace std;
const unsigned int DIV = 1e9 + 9;
struct Mod {
  unsigned int num;
  Mod(unsigned int x) : num(x) {}
  Mod(int x) : num(x) {}
  void write() { cout << num; }
};
Mod operator+(const Mod a, const Mod b) { return Mod((a.num + b.num) % DIV); }
Mod operator-(const Mod a, const Mod b) {
  return Mod((DIV + a.num - b.num) % DIV);
}
Mod operator*(const Mod a, const Mod b) {
  return Mod((unsigned int)(((unsigned long long)a.num * b.num) % DIV));
}
Mod& operator+=(Mod& a, const Mod b) { return a = a + b; }
Mod& operator-=(Mod& a, const Mod b) { return a = a - b; }
Mod& operator*=(Mod& a, const Mod b) { return a = a * b; }
int main() {
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;
  Mod result(0);
  result += 2;
  Mod waysAmount(4), waysFactor(1);
  for (int spikesAmount = (n - 4) / 2, i = 0; i <= spikesAmount; ++i) {
    waysAmount *= waysFactor;
    waysFactor = 2 * (waysFactor + 3) - 3;
    result += waysAmount;
  }
  result *= result;
  result += 1;
  result *= 2;
  result.write();
  return 0;
}
