#include <bits/stdc++.h>
using namespace std;
long long int n, i, f, g, h, ans;
int main() {
  scanf("%I64d", &n);
  n = (n >> 1) - 1;
  f = 1;
  g = 2;
  h = 1;
  for (i = 0; i < n; i++) {
    h = h * f % 1000000009ll;
    g = (g + h * 4) % 1000000009ll;
    f = (f * 2 + 3) % 1000000009ll;
  }
  ans = (g * g * 2 + 2) % 1000000009ll;
  printf("%I64d", ans);
  return 0;
}
