#include <bits/stdc++.h>
using namespace std;
long long n, ans, tmp;
long long qpow(long long x, long long y) {
  long long ans = 1;
  for (; y; y >>= 1, x = x * x % 1000000009)
    if (y & 1) ans = ans * x % 1000000009;
  return ans;
}
int main() {
  cin >> n;
  ans++;
  if (n == 2) {
    cout << 10;
    return 0;
  }
  for (int i = (n - 4) / 2; i >= 1; i--) {
    long long kk = tmp + 4LL;
    kk %= 1000000009;
    kk = kk * qpow(2, i) % 1000000009;
    tmp = (tmp + 4LL) * ((qpow(2, i + 2) - 3LL + 1000000009) % 1000000009) %
          1000000009;
  }
  ans = (ans + (tmp + 6) * (tmp + 6) % 1000000009) % 1000000009;
  ans = ans * 2 % 1000000009;
  cout << ans;
  return 0;
}
