#include <bits/stdc++.h>
int f[1000010], g[1000010], mi[1000010];
int main() {
  f[1] = 1;
  f[2] = 3;
  g[1] = 1;
  g[2] = 1;
  int n;
  scanf("%d", &n);
  mi[0] = 1;
  for (int i = 1; i <= n; i++) mi[i] = mi[i - 1] * 2 % 1000000009;
  for (int i = 3; i <= n; i++) {
    if (i % 2 == 0) {
      g[i] = g[i - 1];
      f[i] = (f[i - 1] + g[i - 1] * 2 % 1000000009) % 1000000009;
    } else {
      g[i] = 1ll * g[i - 1] * (mi[i / 2 + 1] - 3) % 1000000009;
      f[i] = (f[i - 1] + 1ll * g[i - 1] * (mi[i / 2 + 2] - 6)) % 1000000009;
    }
  }
  printf("%lld",
         (1ll * (f[n] - 1) * (f[n] - 1) % 1000000009 * 2 + 2) % 1000000009);
  return 0;
}
