#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; 
}