#include <stdio.h>
#define MOD 1048576

int T[5] = {0,1,2,6,12};
int n,t1,t2,t3,x,y,rez,i;

int main(){
  FILE *f = fopen("12perm.in","r");
  fscanf(f,"%d",&n);
  fclose(f);
  if (n<=4) {
    rez = T[n];
  } else {
    t1=12;
    t2=6;
    t3=2;

    for (i=5;i<=n;i++) {
      x = (t1+t3+((i-2)<<1))%MOD;
      t3=t2;
      t2=t1;
      t1=x;
    }
    rez = x;
  }
  FILE *g = fopen("12perm.out","w");
  fprintf(g,"%d",rez);
  fclose(g);

  return 0;
}