#include<stdio.h>
#define mod 1048576
long long t[5],n,i;
int main()
{freopen("12perm.in","r",stdin);
 freopen("12perm.out","w",stdout);
 scanf("%lld",&n);
 t[1]=1;t[2]=2;t[3]=6;t[4]=12;
 if(n<=4) printf("%lld",t[n]);
 else {for(i=5;i<n;i++)
 {t[0]=t[3]+t[1]+2*(i-2);
  if(t[0]>mod) t[0]-=mod;
  t[1]=t[2];t[2]=t[3];t[3]=t[4];t[4]=t[0];}
 printf("%lld",t[4]);}
 return 0;}