#include <bits/stdc++.h>
using namespace std;
using cat = long long;
int main() {
  cin.sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(10);
  int N;
  cin >> N;
  cat ans = 1, pr = 4, mod = 1000000009;
  for (int i = 0, k = 1; i <= N / 2 - 2; i++, k = ((k + 1) * 2LL + 1) % mod) {
    pr = pr * k % mod;
    ans += pr;
    if (ans >= mod) ans -= mod;
  }
  ans = ((ans + 1) * (ans + 1) % mod * 2 + 2) % mod;
  cout << ans << "\n";
  return 0;
}
