#include <cstdio>
#define mod 1048576

int main()
{
  long long ti, ti1,ti2, ti3;
  int n, i;
  freopen("12perm.in", "r", stdin);
  scanf("%d\n", &n);

  if(n==1) {printf("1\n"); return 0;}
  if(n==2) { printf("2\n"); return 0;}
  if(n==3) { printf("6\n"); return 0;}
  if(n==4) { printf("12\n"); return 0;}

  ti1=12;
  ti2=6;
  ti3=2;

  for(i=5;i<=n;i++)
    {
      ti=ti1+ti3+((i-2)<<1);
      // ti=ti1;
      //ti%=mod;
      //ti+=ti3;
      //ti%=mod;
      //ti+=2*(i-2);
      //ti%=mod; 

      ti3=ti2;
      ti2=ti1;
      ti1=ti;
	  while(ti>mod) ti-=mod;
	  while(ti1>mod) ti1-=mod;
	  while(ti2>mod) ti2-=mod;
	  while(ti3>mod) ti3-=mod;
    //  ti=ti%mod;
    //  ti1=ti1%mod;
   //   ti2=ti2%mod;
    //  ti3=ti3%mod;
    }
  freopen("12perm.out", "w", stdout);
  printf("%lld\n", ti%mod);
  return 0;
}