#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 <long long int> v(n+5,0);
		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] - v[i - 5] + 4 + mod ) % mod;

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