# include <fstream>

using namespace std;

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

#define MOD 1048576

long a,b,c,d,e,n,i,aux;

int main ()
{
	ifstream fin ( input ) ;
	ofstream fout ( output ) ;

	fin >> n;

	if(n == 1)
	{
		fout << 1;
		return 0;
	}
	if(n == 2)
	{
	   fout<< 2;
		return 0;
	}
	if(n == 3)
	{
		fout << 6;
		return 0;
	}
	if(n == 4)
	{
		fout << 12;
		return 0;
	}
	if(n == 5)
	{
		fout << 20;
		return 0;
	}
	if(n == 6)
	{
		fout << 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;
		
	
    }

	fout << t_i;

	return 0;
}