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