#include <bits/stdc++.h>
using namespace std;
const int maxn = 1100000;
const int maxp = 1000000009;
static int n;
int main() {
  long long A = 1, B = 4, C = 2, D = 1;
  scanf("%d\n", &n);
  if (n == 2)
    printf("10\n");
  else {
    n /= 2;
    A += 4;
    for (int i = 3; i <= n; i++) {
      C = C * 2 % maxp;
      D = (D + C) % maxp;
      B = B * D % maxp;
      A = (A + B) % maxp;
    }
    A = ((A + 1) * (A + 1) * 2 + 2) % maxp;
    cout << A << endl;
  }
  return 0;
}
