#include <fstream>
#include <vector>

using namespace std;

ifstream in("12perm.in");
ofstream out("12perm.out");

constexpr int mod=1048576;
long long N;

class Matrix
{
public:
	int n, m;
	vector<vector<long long>> elems;

	Matrix()
	{

	}

	Matrix(int n, int m)
	{
		this->n = n;
		this->m = m;
		
		elems = vector<vector<long long>> (n, vector<long long>(m , 0));
	}

	Matrix operator * (const Matrix& operand)
	{
		Matrix result(n, operand.m);

		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < operand.m; j++)
			{
				for (int k = 0; k < m; k++)
				{
					result.elems[i][j] += elems[i][k] * operand.elems[k][j];
				}
				result.elems[i][j] %= mod;
			}
		}
		return result;
	}
};

Matrix matrixExp(Matrix mat, long long exp)
{
	if(exp == 1)
		return mat;
	Matrix result(mat.n, mat.n);

	if(exp % 2 == 0)
	{
		return matrixExp(mat, exp / 2) * matrixExp(mat, exp / 2);
	}
	else
	{
		return matrixExp(mat, exp - 1) * mat;
	}

	return result;
}

int main()
{
	in>>N;
	if (N == 1)
	{
		out<<1;
		return 0;
	}
	if (N == 2)
	{
		out<<2;
		return 0;
	}
	if (N == 3)
	{
		out<<6;
		return 0;
	}
	if (N == 4)
	{
		out<<12;
		return 0;
	}
	
	Matrix mat1(5, 5);
	mat1.elems = {
		{1, 0, 0, 0, 0},
		{0, 1, 1, 0, 0},
		{1, 0, 0, 1, 0},
		{0, 1, 0, 0, 0},
		{0, 1, 0, 0, 1}
	};

	Matrix mat2(1, 5);
	mat2.elems = {{ 0, 2, 2, 0, 2 }};

	mat1 = matrixExp(mat1, N - 3);
	mat2 = mat2 * mat1;
	
	out<<(mat2.elems[0][0] + mat2.elems[0][1] + mat2.elems[0][2] + mat2.elems[0][3] + mat2.elems[0][4]) % mod;

	return 0;
}