#include <stdio.h>
#define mod 0x100000
int main ()
{freopen("12perm.in","r",stdin);
 freopen("12perm.out","w",stdout);
 int a[3],b[3],c[3],i;
 scanf("%d",&i);
 switch(i)
 {case 1:printf("1");return 0;
  case 2:printf("2");return 0;
  case 3:printf("6");return 0;
 }
 a[1]=2;
 b[1]=2;
 c[1]=2;
 a[2]=4;
 b[2]=4;
 c[2]=4;
 for (i-=3;i;--i)
 {a[0]=a[1];a[1]=a[2];
  b[0]=b[1];b[1]=b[2];
  c[0]=c[1];c[1]=c[2];
  
  a[2]=(a[1]+b[1])%mod;
  b[2]=(a[0]+2)%mod;
  c[2]=(a[1]+c[1])%mod;
 }
 printf("%d",(a[2]+c[2]-a[0]-b[0])%mod);
 return 0;
}