#include<fstream>
using namespace std;

const int mod=1048576;

int v[10];
long long i,n;
long 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);
       a4=a4%mod;
       a1=a2;  a2=a3;   a3=a4;
       }
  printf("%d",a4);     
  } 
   
return 0;}