#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 - 1);
		}
				

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