#include <bits/stdc++.h>
using namespace std;
int f[1000010], n, now = 1, tmp = 1;
int main() {
  scanf("%d", &n), f[1] = 1;
  for (int i = 2; i <= n; i++)
    f[i] = (f[i - 1] * 2 % 1000000009 + 3) % 1000000009;
  for (int i = 2; i + 2 <= n; i += 2)
    (now += 4ll * tmp % 1000000009 * f[i / 2] % 1000000009) %= 1000000009,
        tmp = 1ll * tmp * f[i / 2] % 1000000009;
  if (n & 1)
    (now += 2ll * tmp % 1000000009 * (n - 2) % 1000000009) %= 1000000009;
  printf("%lld\n", (1ll * now * 4 + 2ll * now * now + 4) % 1000000009);
}
