#include <bits/stdc++.h>
using namespace std;
long long a[1000001], b[1000001];
long long ans, tmp;
int n;
int main() {
  a[1] = 4;
  b[0] = 1;
  cin >> n;
  for (int i = 2; i <= n; ++i) a[i] = (a[i - 1] * 2 + 4) % 1000000009;
  for (int i = 1; i <= n; ++i) b[i] = (b[i - 1] * (a[i] + 1)) % 1000000009;
  if (n == 2) ans = 5;
  if (n == 4) ans = 37;
  if (n > 4) {
    tmp = 4;
    for (int i = 1; i <= n / 2 - 2; ++i) tmp = (tmp + b[i] * 4) % 1000000009;
    ans = (5 + 4 * tmp + tmp * tmp) % 1000000009;
  }
  cout << (ans * 2) % 1000000009 << endl;
}
