#include<cstdio>
#define mod 1048576


int v[5];
long i,n;
long a4,a3,a2,a1;

int main()
{freopen("12perm.in","r",stdin);
freopen("12perm.out","w",stdout);
scanf("%d",&n);
v[1]=1;  v[2]=2;  v[3]=6;  v[4]=12;
if(n<=4)
  printf("%d",v[n]);
else
 {a3=v[4];  a2=v[3];  a1=v[2];
  for(i=5; i<=n; i++)
       {
       a4=(a3+a1+2*(i-2))%mod;
       a1=a2;  a2=a3;  a3=a4;
       }
  printf("%d",a4);     
  } 
   
return 0;}