#include <stdio.h>
#include <string.h>

#define CONST (1048575)

int main() {
	int N, oldc[8] = {1,1,1,1,0,1,1}, newc[8] = {0,0,0,0,0,0,0}, sol, oldN;
	int cc[16][8] = {
		{1,1,1,1,0,1,1},
		{973303,973303,473518,473518,893644,325593,325593},
		{675700,675700,186397,186397,869924,323800,323800},
		{417775,417775,198607,198607,475646,455097,455097},
		{544186,544186,135730,135730,699866,428145,428145},
		{108624,108624,868188,868188,342234,397806,397806},
		{603675,603675,950866,950866,546268,735280,735280},
		{118913,118913,469375,469375,808066,893312,893312},
		{20855,20855,256686,256686,283724,638553,638553},
		{921332,921332,446365,446365,464036,96472,96472},
		{252655,252655,146639,146639,721534,1045049,1045049},
		{47418,47418,1042738,1042738,103258,266609,266609},
		{865104,865104,305116,305116,360538,244206,244206},
		{359707,359707,965586,965586,767836,677552,677552},
		{499969,499969,824063,824063,862466,197376,197376},
		{428279,428279,547758,547758,263628,640217,640217}};
	
	freopen("12perm.in", "r", stdin);
	freopen("12perm.out", "w", stdout);

	scanf("%d" ,&N); oldN = N;
	memcpy(oldc, cc[N/1000000], sizeof(oldc));
	if(N < 1000000)
		N -= 3;
	else N %= 1000000;
	for(; N > 0; -- N) {
		newc[0] = oldc[5]+1; newc[0] &= CONST;
		newc[1] = oldc[6]+1; newc[1] &= CONST;
		newc[2] = oldc[0]+oldc[2]; newc[2] &= CONST;
		newc[3] = oldc[1]+oldc[3]; newc[3] &= CONST;
		newc[4] = oldc[4]+oldc[5]+oldc[6]; newc[4] &= CONST;
		newc[5] = oldc[2];
		newc[6] = oldc[3];
		memcpy(oldc, newc, sizeof(oldc));
	}

	N = oldN;
	if(N == -2)
		sol = 1;
	else if(N == -1)
		sol = 2;
	else for(sol = N = 0; N < 7; ++ N) {
		sol += oldc[N];
		sol &= CONST;
	}

	printf("%d\n", sol);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}