#include<fstream>
#define MOD (1<<20)-1
std::ifstream f("12perm.in");
std::ofstream g("12perm.out");
int n,a[4],i;
int main()
{ f>>n;
  a[0]=1;
  a[1]=2;
  a[2]=6;
  a[3]=12;
  if(n<5) g<<a[n-1]<<"\n";
  n-=4;
  i=3;
  while(n){ a[0]=a[1];a[1]=a[2];a[2]=a[3];a[3]=a[2]+a[0]+2*(i++);a[3]&=MOD;--n;}
  g<<a[3]<<"\n";
  f.close();
  g.close();
  return 0;
}