# include <stdio.h>

# define input "12perm.in"
# define output "12perm.out"

# define mod 1048576

int x,y,z,i,n;
int res;

int main()
{
    freopen(input, "r", stdin);
    freopen(output, "w", stdout);
    
    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;
    }
    x = 2;
    y = 6;
    z = 12;
    
    for(i=5;i<=n;i++)
    {                     
        res = z + x + 2*(i-2);
        res%=mod;
        x = y;
        y = z;
        z = res;
    }
    
    printf("%d",res);
    
    return 0;
}