#include <fstream>

using namespace std ;

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

const long long int mod = 1048576;

int main()
{
		long long int n;
		fin >> n;
		fin.close();
	
		int c  = 6;
		int d  = 12;
		int e  = 20;
		int f  = 34;
		int g  = 56;
		int h  = 88;

		for ( int i = 9 ; i <= n ; i++)
		{
				c =d;
				d = e;
				e = f;
				f = g;
				g = h;

				h = ( g + f + 4- c + mod ) % mod;
		}
				

		fout << h ;
		fout.close();
		return 0;
}