# include <stdio.h>



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

#define MOD 1048576

long n, i;

int main ()
{
	freopen( input, "r", stdin ) ;
	freopen ( output, "w", stdout ) ;

	scanf("%ld",&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;
	}
	if(n == 5)
	{
		printf("20");
		return 0;
	}
	if(n == 6)
	{
		printf("34");
		return 0;
	}

	long ti_3 = 12;
	long ti_2 = 20;
	long ti_1 = 34;

    long t_i;

	for(i = 7;i<=n; ++ i)
	{
    
        t_i = ti_1 + ti_3 + 2 * (i - 2);
		t_i%=MOD;
		
              		
		ti_3 = ti_2;	
		ti_2 = ti_1;
		ti_1 = t_i;
		
	
    }

	printf("%ld", t_i);

	return 0;
}