#include<cstdio>
#define mod 1048576
int main ()
{freopen ("12perm.in","r",stdin);
freopen ("12perm.out","w",stdout);
int n,i,a,b,c,d,e,x;
scanf("%d",&n);
if(n==1)
    {printf("1");
    return 0;
    }
if(n==2)
    {printf("2");
    return 0;
    }
if(n==3)
    {printf("6");
    return 0;
    }
if(n==4)
    {printf("12");
    return 0;
    }
a=1;
b=2;
c=6;
d=12;
x=6;
for(i=5;i<=n;i++)
    {e=(b+d+x)%mod;
    x+=2;
    a=b;
    b=c;
    c=d;
    d=e;
    }
printf("%d",e);
return 0;
}