#include<stdio.h>
#define ko 1048576
long lung1,lung2,lung3,lung,nr,l,n,i;

long init()
{lung1=2;
 lung2=2;
 lung3=4;
 nr=6;
 return 4;
 }

int main()
{freopen("12perm.in","r",stdin);
 scanf("%ld",&n);

 i=init();

 for(;i<=n;i++)
  {lung=(lung1+lung3)%ko;
   l=lung3;
   lung2=lung3;
   lung1=lung2;
   lung3=lung;
   nr=(nr+l)%ko;
   }

 freopen("12perm.out","w",stdout);
 printf("%ld",nr+(lung-l));
 fclose(stdout);
 return 0;
 }