#include <stdio.h>
#define MOD (1 << 20)
#define MAXN 15000000
int d[4];

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