#include <bits/stdc++.h>
using namespace std;
using ll = long long unsigned int;
ll dp[1000100], endL[1000100], fillLine[1000100], mod = 1000000009;
int main() {
  int n;
  cin >> n;
  dp[0] = 1;
  dp[2] = 3;
  fillLine[0] = 1;
  fillLine[1] = 5;
  endL[2] = 1;
  endL[0] = 1;
  ll prod = 2;
  for (int i = 2; i < 1000100; i++) {
    fillLine[i] = fillLine[i - 1] + prod * 4;
    fillLine[i] %= mod;
    prod *= 2;
    prod %= mod;
  }
  for (int i = 4; i <= n; i += 2) {
    endL[i] = (endL[i - 2] * (fillLine[(i / 2 - 2)])) % mod;
    dp[i] = (dp[i - 2] + 4 * endL[i - 2] * fillLine[(i / 2 - 2)]) % mod;
  }
  ll ANS = (((dp[n] - 1) * (dp[n] - 1) + 1) * 2) % mod;
  cout << ANS;
  return 0;
}
