#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:1000000000")
using namespace std;
const bool db = false;
int main() {
  long long a = 1, b = 2, c = 4;
  int n;
  cin >> n;
  for (--n, --n; n > 0; --n, --n) {
    c = c * a % (1000000007 + 2);
    b = (b + c) % (1000000007 + 2);
    a = (2 * a + 3) % (1000000007 + 2);
  }
  cout << (2 * b * b + 2) % (1000000007 + 2) << "\n";
  getchar();
  getchar();
  return 0;
}
