#include<cstdio>
#define mod 1048576
int main ()
{freopen ("12perm.in","r",stdin);
freopen ("12perm.out","w",stdout);
int n,i,k,a,c,a1,c1,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;
    }
a1=6;
c1=2;
k=2;
for(i=5;i<n;i++)
    {c=(c1+k)%mod;
    k=(k+2)%mod;
    a=(2*a1+c1+2-c)%mod;
    a1=a;
    c1=c;
    }
printf("%d",2*a1+c1+6);
return 0;
}