#include <bits/stdc++.h>
using namespace std;
struct huge {
  static char s[5 * 10];
  long long a[5];
  int len;
  void clear() {
    len = 1;
    a[len] = 0;
  }
  huge() { clear(); }
  huge(long long x) { *this = x; }
  huge(char s[]) { this->str(s); }
  huge operator=(huge b) {
    len = b.len;
    for (int i = 1; i <= len; ++i) a[i] = b.a[i];
    return *this;
  }
  huge operator+(huge b) {
    int L = len > b.len ? len : b.len;
    huge tmp;
    for (int i = 1; i <= L + 1; ++i) tmp.a[i] = 0;
    for (int i = 1; i <= L; ++i) {
      if (i > len)
        tmp.a[i] += b.a[i];
      else if (i > b.len)
        tmp.a[i] += a[i];
      else {
        tmp.a[i] += a[i] + b.a[i];
        if (tmp.a[i] >= 100000000) {
          tmp.a[i] -= 100000000;
          ++tmp.a[i + 1];
        }
      }
    }
    if (tmp.a[L + 1])
      tmp.len = L + 1;
    else
      tmp.len = L;
    return tmp;
  }
  huge operator-(huge b) {
    int L = len > b.len ? len : b.len;
    huge tmp;
    for (int i = 1; i <= L + 1; ++i) tmp.a[i] = 0;
    for (int i = 1; i <= L; ++i) {
      if (i > b.len) b.a[i] = 0;
      tmp.a[i] += a[i] - b.a[i];
      if (tmp.a[i] < 0) {
        tmp.a[i] += 100000000;
        --tmp.a[i + 1];
      }
    }
    while (L > 1 && !tmp.a[L]) --L;
    tmp.len = L;
    return tmp;
  }
  huge operator*(huge b) {
    int L = len + b.len;
    huge tmp;
    for (int i = 1; i <= L; ++i) tmp.a[i] = 0;
    for (int i = 1; i <= len; ++i)
      for (int j = 1; j <= b.len; ++j) {
        tmp.a[i + j - 1] += a[i] * b.a[j];
        if (tmp.a[i + j - 1] >= 100000000) {
          tmp.a[i + j] += tmp.a[i + j - 1] / 100000000;
          tmp.a[i + j - 1] %= 100000000;
        }
      }
    tmp.len = len + b.len;
    while (tmp.len > 1 && !tmp.a[tmp.len]) --tmp.len;
    return tmp;
  }
  pair<huge, huge> divide(huge a, huge b) {
    int L = a.len;
    huge c, d;
    for (int i = L; i; --i) {
      c.a[i] = 0;
      d = d * 100000000;
      d.a[1] = a.a[i];
      int l = 0, r = 100000000 - 1, mid;
      while (l < r) {
        mid = (l + r + 1) >> 1;
        if (b * mid <= d)
          l = mid;
        else
          r = mid - 1;
      }
      c.a[i] = l;
      d -= b * l;
    }
    while (L > 1 && !c.a[L]) --L;
    c.len = L;
    return make_pair(c, d);
  }
  huge operator/(long long x) {
    long long d = 0;
    huge tmp;
    for (int i = len; i; --i) {
      d = d * 100000000 + a[i];
      tmp.a[i] = d / x;
      d %= x;
    }
    tmp.len = len;
    while (tmp.len > 1 && !tmp.a[tmp.len]) --tmp.len;
    return tmp;
  }
  long long operator%(long long x) {
    long long d = 0;
    for (int i = len; i; --i) d = (d * 100000000 + a[i]) % x;
    return d;
  }
  huge operator/(huge b) { return divide(*this, b).first; }
  huge operator%(huge b) { return divide(*this, b).second; }
  huge &operator+=(huge b) {
    *this = *this + b;
    return *this;
  }
  huge &operator-=(huge b) {
    *this = *this - b;
    return *this;
  }
  huge &operator*=(huge b) {
    *this = *this * b;
    return *this;
  }
  huge operator/=(huge b) {
    *this = *this / b;
    return *this;
  }
  huge operator%=(huge b) {
    *this = *this % b;
    return *this;
  }
  huge &operator++() {
    huge T;
    T = 1;
    *this = *this + T;
    return *this;
  }
  huge &operator--() {
    huge T;
    T = 1;
    *this = *this - T;
    return *this;
  }
  huge operator++(int) {
    huge T, tmp = *this;
    T = 1;
    *this = *this + T;
    return tmp;
  }
  huge operator--(int) {
    huge T, tmp = *this;
    T = 1;
    *this = *this - T;
    return tmp;
  }
  huge operator+(long long x) {
    huge T;
    T = x;
    return *this + T;
  }
  huge operator-(long long x) {
    huge T;
    T = x;
    return *this - T;
  }
  huge operator*(long long x) {
    huge T;
    T = x;
    return *this * T;
  }
  huge operator*=(long long x) {
    *this = *this * x;
    return *this;
  }
  huge operator+=(long long x) {
    *this = *this + x;
    return *this;
  }
  huge operator-=(long long x) {
    *this = *this - x;
    return *this;
  }
  huge operator/=(long long x) {
    *this = *this / x;
    return *this;
  }
  huge operator%=(long long x) {
    *this = *this % x;
    return *this;
  }
  bool operator==(long long x) {
    huge T;
    T = x;
    return *this == T;
  }
  bool operator!=(long long x) {
    huge T;
    T = x;
    return *this != T;
  }
  bool operator<=(long long x) {
    huge T;
    T = x;
    return *this <= T;
  }
  bool operator>=(long long x) {
    huge T;
    T = x;
    return *this >= T;
  }
  bool operator<(long long x) {
    huge T;
    T = x;
    return *this < T;
  }
  bool operator>(long long x) {
    huge T;
    T = x;
    return *this > T;
  }
  huge operator=(long long x) {
    len = 0;
    while (x) a[++len] = x % 100000000, x /= 100000000;
    if (!len) a[++len] = 0;
    return *this;
  }
  bool operator<(huge b) {
    if (len < b.len) return 1;
    if (len > b.len) return 0;
    for (int i = len; i; --i) {
      if (a[i] < b.a[i]) return 1;
      if (a[i] > b.a[i]) return 0;
    }
    return 0;
  }
  bool operator==(huge b) {
    if (len != b.len) return 0;
    for (int i = len; i; --i)
      if (a[i] != b.a[i]) return 0;
    return 1;
  }
  bool operator!=(huge b) { return !(*this == b); }
  bool operator>(huge b) { return !(*this < b || *this == b); }
  bool operator<=(huge b) { return (*this < b) || (*this == b); }
  bool operator>=(huge b) { return (*this > b) || (*this == b); }
  void str(char s[]) {
    int l = strlen(s);
    long long x = 0, y = 1;
    len = 0;
    for (int i = l - 1; i >= 0; --i) {
      x = x + (s[i] - '0') * y;
      y *= 10;
      if (y == 100000000) a[++len] = x, x = 0, y = 1;
    }
    if (!len || x) a[++len] = x;
  }
  void read() {
    scanf("%s", s);
    this->str(s);
  }
  void print() {
    printf("%d", (int)a[len]);
    for (int i = len - 1; i; --i) {
      for (int j = 100000000 / 10; j >= 10; j /= 10) {
        if (a[i] < j)
          printf("0");
        else
          break;
      }
      printf("%d", (int)a[i]);
    }
    printf("\n");
  }
};
char huge::s[5 * 10];
int main() {
  const int P = 1000000009;
  huge f = 1, p = 2, t = 4, n, ans;
  n.read();
  int t1 = clock();
  for (; n > 2; t = t * f % P, p = (p + t) % P, f = (f * 2 + 3) % P, n -= 2)
    ;
  ans = (p * p + 1) * 2 % P;
  ans.print();
  return 0;
}
