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