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