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