#include <stdio.h>   
  
#define Mod 1048576   
#define Nmax 15000000
  
int n,T[Nmax],i;   
  
int main()   
{   
freopen("12perm.in","r",stdin);   
freopen("12perm.out","w",stdout);   
  
scanf("%lld",&n);   
  
T[1]=1;T[2]=2;T[3]=6;T[4]=12;
for (i=5;i<=n;i++)   
    T[i]=(T[i-1]+T[i-3]+2*(i-2))%Mod;
  
printf("%lld",T[n]);
return 0;   
}