#include <cstdio>

const int MAXN = 1e7 + 6e6;
#define MOD (1 << 20)

int v[MAXN + 1];

int main() {
  int n;
  FILE *f = fopen("12perm.in", "r");
  fscanf(f, "%d", &n);
  fclose(f);
  v[1] = 1;
  v[2] = 2;
  v[3] = 6;
  v[4] = 12;
  for (int i = 5; i <= n; ++i) {
    v[i] = ((1LL * 2 * (i - 2) & (MOD - 1)) + v[i - 1] + v[i - 3]) & (MOD - 1);
  }
  f = fopen("12perm.out", "w");
  fprintf(f, "%d\n", v[n]);
  fclose(f);
  return 0; 
}

/*
#include <bits/stdc++.h>

std::vector <int> v;

int main() {
  int n, ans;
  bool check;             
  FILE *f = fopen("12perm.in", "r");
  scanf("%d", &n);
  fclose(f);
  for (int k = 1; k <= n; ++k) {
    for (int i = 1; i <= k; ++i) {
      v.push_back(i);
    }          
    ans = 0;
    do {
      for (int i = 1; i < k; ++i) {
        check = 0;
        if (std::abs(v[i] - v[i - 1]) > 2) {
          check = 1;
          break;
        }
      }
      if (!check) ++ans;
    } while (next_permutation(v.begin(), v.end()));
    printf("r[%d] = %d\n", k, ans);
    v.clear();
  }
  return 0;
} */