#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000009;
long long seq;
long long bin[1000050];
long long cur[1000050];
int main() {
  int n;
  cin >> n;
  bin[0] = 1;
  cur[1] = 1;
  for (int i = 1; i <= n; ++i) bin[i] = bin[i - 1] * 2, bin[i] %= mod;
  for (int i = 2; i <= n; ++i) cur[i] = cur[i - 1] * (bin[i] - 3) % mod;
  for (int i = 2; i <= n / 2; i++) {
    long long tmp = cur[i] * 4;
    tmp %= mod;
    seq += tmp;
    seq %= mod;
  }
  cout << ((2 * (seq * seq % mod) % mod + 8 * seq % mod) % mod + 10) % mod
       << endl;
}
