#include <fstream>
#include <algorithm>
#include <vector>

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();

		vector <int> v(n+5,0);

		v[1] = 1;
		v[2] = 2;
		v[3] = 6;
		v[4] = 12;
		v[5] = 20;
		v[6] = 34;
		v[7] = 56;

		for ( int i = 8 ; i <= n ; i++)
		{
				v[i] = (v[i-1] + v[i-2] + 4 - v[i-5] + mod) % mod;
		}
				

		fout << v[n] ;
		fout.close();
		return 0;
}