#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000009;
int pow2[1234567];
int main() {
  pow2[0] = 1;
  for (int i = (1), _b(1234567); i < _b; ++i) {
    pow2[i] = pow2[i - 1] * 2;
    pow2[i] %= mod;
  }
  long long n;
  cin >> n;
  n /= 2;
  if (n == 1) {
    cout << 10 << endl;
    return 0;
  }
  long long res = 0;
  long long now = 0;
  for (int d = n - 2; d >= 0; --d) {
    now += 4;
    now = ((now * (pow2[d + 2] - 3)) % mod + mod) % mod;
  }
  now += 2;
  now *= now;
  now %= mod;
  now *= 2;
  now %= mod;
  now += 2;
  now %= mod;
  cout << now << endl;
  return 0;
}
