#include<fstream.h>
#define max 1048576
 ifstream f("12perm.in");
 ofstream g("12perm.out");
 long long r1,r2,r3,r4,n,i,aux;
int main()
{
 f>>n;
 r1=1;
 r2=2;
 r3=6;
 r4=12;
 for(i=5;i<=n;i++)
 {
  aux=r4;
  r4=(r4+r2+2*(i-2))&(max-1);
  r2=r3;
  r3=aux;
 }
 g<<r4;
 g.close();
 f.close();
 return 0;

}