#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  long long int a, b, c, r, m;
  m = 1000000009;
  a = 1;
  b = 2;
  c = 4;
  cin >> n;
  while (n > 2) {
    c *= a;
    c %= m;
    b += c;
    b %= m;
    a = a * 2 + 3;
    a %= m;
    n -= 2;
  }
  r = b * b + 1;
  r *= 2;
  cout << r % m << endl;
  return 0;
}
