#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]=1;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]%Mod);   
return 0;   
}