#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;

const char infile[] = "12perm.in";
const char outfile[] = "12perm.out";

#define MODULO 1048576

class BMatrix
{
public:
	BMatrix(int rows, int columns);
	BMatrix(int order);
	virtual ~BMatrix();

	BMatrix(const BMatrix& other);
	BMatrix& operator = (BMatrix& other);


	BMatrix power(int power);
	BMatrix operator *(BMatrix other);
	BMatrix& operator *=(BMatrix other);

	int* operator [](int row);
	int getRowCount();
	int getColumnCount();

	friend std::ostream& operator << (std::ostream& stream, BMatrix& matrix);

protected:

private:
	int** _data;
	int _rows;
	int _columns;
};

BMatrix toBMatrix(int data[][5], int rows);

int MOD(int value)
{
	return value & (MODULO - 1);
}

void solve(istream& fin, ostream& fout)
{
	int N;
	fin >> N;

	if(N <= 4)
	{
		int answer;
		switch(N)
		{
		case 1:
			answer = 1;
			break;
		case 2:
			answer = 2;
			break;
		case 3:
			answer = 6;
			break;
		case 4:
			answer = 12;
			break;
		}
		fout << answer << "\n";
		return;
	}


	int initial[1][5] = { 
		{1, 1, 0, 1, 0 }
	};
	int recurence[5][5] = {
		{0, 0, 1, 0, 1},
		{1, 1, 0, 0, 0},
		{0, 1, 0, 0, 0},
		{0, 1, 0, 1, 0},
		{0, 0, 0, 0, 1}
	};

	BMatrix m1(1); 
	BMatrix m2(1); 

	m1 = toBMatrix(initial, 1);
	m2 = toBMatrix(recurence, 5);

	BMatrix m3(1);

	m3 = m2.power(N- 4);
	m3 = m1 * m3;

	int result = 0;
	result += MOD(m3[0][0] * 4);
	result += MOD(m3[0][1] * 4);
	result += MOD(m3[0][2] * 2);
	result += MOD(m3[0][3] * 4);
	result += MOD(m3[0][4] * 2);
	result = MOD(result);

	fout << result
		 << "\n";

}


int main(int argc, char* argv[])
{

	fstream fin(infile, ios::in);
	fstream fout(outfile, ios::out);

	solve(fin, fout);

	fin.close();
	fout.close();
}

//------------------------------------------------------------



BMatrix toBMatrix(int data[][5], int rows)
{
	BMatrix result(rows, 5);

	for(int i = 0; i < rows; i++)
	{
		for(int j = 0 ; j < 5; j++)
		{
			result[i][j] = data[i][j];
		}
	}
	return result;
}



BMatrix::BMatrix( int rows, int columns )
{
	this->_rows = rows;
	this->_columns = columns;

	this->_data = new int*[this->_rows];

	for(int i = 0; i < this->_rows; i++)
	{
		this->_data[i] = new int[this->_columns];
		memset(this->_data[i], 0, sizeof(int) * this->_columns);
	}

}

BMatrix::BMatrix( int order )
{
	this->_rows = order;
	this->_columns = order;
	this->_data = new int*[this->_rows];

	for(int i = 0; i < this->_rows; i++)
	{
		this->_data[i] = new int[this->_columns];
		memset(this->_data[i], 0, sizeof(int) * this->_columns);
	}
}

BMatrix::BMatrix( const BMatrix& other )
{
	this->_rows = other._rows;
	this->_columns = other._columns;

	this->_data = new int*[this->_rows];

	for(int i = 0; i < this->_rows; i++)
	{
		this->_data[i] = new int[this->_columns];
		memcpy(this->_data[i], other._data[i], sizeof(int) * this->_columns);
	}
}

BMatrix::~BMatrix()
{
	for(int i = 0; i < this->_rows; i++)
	{
		delete this->_data[i];
	}
	delete this->_data;
}


BMatrix& BMatrix::operator=( BMatrix& other )
{
	if(this->_rows != other._rows || this->_columns != other._columns)
	{
		for(int i = 0; i < this->_rows; i++)
		{
			delete this->_data[i];
		}
		delete this->_data;

		this->_rows = other._rows;
		this->_columns = other._columns;

		this->_data = new int*[this->_rows];
	}

	for(int i = 0; i < this->_rows; i++)
	{
		this->_data[i] = new int[this->_columns];
		memcpy(this->_data[i], other._data[i], sizeof(int) * this->_columns);
	}
	return *this;
}

BMatrix BMatrix::power( int power )
{
	BMatrix current(*this);
	BMatrix result(this->_rows);

	for(int i = 0 ; i < this->_rows; i++)
	{
		result[i][i] = 1;
	}

	for(int i = 0; i <= 31; i++)
	{

		if( (1<<i) & power)
		{
			result *= current;
		}
		current *= current;
	}
	return result;
}

BMatrix BMatrix::operator*( BMatrix other )
{
	BMatrix result(this->_rows, other._columns);

	for(int i = 0 ; i < this->_rows; i++)
	{
		for(int j = 0; j < other._columns; j++)
		{
			for(int k = 0; k < this->_columns; k++)
			{
				result[i][j] += MOD(this->_data[i][k] * other[k][j]);
				result[i][j] = MOD(result[i][j]);
			}
		}
	}

	return result;
}

BMatrix& BMatrix::operator*=( BMatrix other )
{

	BMatrix result(this->_rows, other._columns);

	for(int i = 0 ; i < this->_rows; i++)
	{
		for(int j = 0; j < other._columns; j++)
		{
			for(int k = 0; k < this->_columns; k++)
			{
				result[i][j] += MOD(this->_data[i][k] * other[k][j]);
				result[i][j] = MOD(result[i][j]);
			}
		}
	}

	this->operator=(result);

	return *this;
}

int* BMatrix::operator[]( int row )
{
	return this->_data[row];
}

int BMatrix::getRowCount()
{
	return this->_rows;
}

int BMatrix::getColumnCount()
{
	return this->_columns;
}


ostream& operator << (ostream& stream, BMatrix& matrix)
{
	for(int i = 0; i < matrix.getRowCount(); i++)
	{
		for(int j = 0; j < matrix.getColumnCount(); j++)
		{
			stream << matrix[i][j] << " ";
		}
		stream << "\n";
	}
	return stream;
}