#include <bits/stdc++.h>
using namespace std;
const int INF = 2147483647;
const long long LLINF = 9223372036854775807;
int main() {
  int n;
  cin >> n;
  long long mod = 1000000009;
  if (n == 2) cout << 10, exit(0);
  long long b = 5, g = 1, r = 6;
  long long fb = 2, fg = 2, t = 4;
  for (int i = 0; i < n / 2 - 2; ++i) {
    b = r + 3 * g * (t + 1);
    g = (g * (1 + t)) % mod;
    r = (b + g) % mod;
    fb = (t + fg * 2) % mod;
    fg = (fg * 2) % mod;
    t = (fg + fb) % mod;
  }
  long long ans = ((r * r + 1) * 2) % mod;
  cout << ans;
  return 0;
}
