#include <iostream>

unsigned int N, a, b, c;

int main() {
	std::cin >> N;
	if (N < 120000) {
		switch (N % 6) {
		case 0: c = 1;
			break;
		case 1: b = 1; c = 2;
			break;
		case 2: a = 1; b = 2; c = 4;
			break;
		case 3: a = 2; b = 4; c = 10;
			break;
		case 4: a = 4; b = 10; c = 24;
			break;
		case 5: a = 10; b = 24; c = 56;
			break;
		}
	}
	else if (N < 240000) {
		N -= 120000;
		switch (N % 6) {
		case 0: a = 19850648; b = 9089956; c = 13284784;
			break;
		case 1: a = 9089956; b = 13284784; c = 5640540;
			break;
		case 2: a = 13284784; b = 5640540; c = 9250884;
			break;
		case 3: a = 5640540; b = 9250884; c = 4651120;
			break;
		case 4: a = 9250884; b = 4651120; c = 373212;
			break;
		case 5: a = 4651120; b = 373212; c = 19248192;
			break;
		}
	}
	else if (N < 360000) {
		N -= 240000;
		switch (N % 6) {
		case 0: a = 10698836; b = 10716036; c = 5181544;
			break;
		case 1: a = 10716036; b = 5181544; c = 11550652;
			break;
		case 2: a = 5181544; b = 11550652; c = 4113160;
			break;
		case 3: a = 11550652; b = 4113160; c = 18589408;
			break;
		case 4: a = 4113160; b = 18589408; c = 19859904;
			break;
		case 5: a = 18589408; b = 19859904; c = 7525912;
			break;
		}
	}
	else if (N < 480000) {
		N -= 360000;
		switch (N % 6) {
		case 0: a = 6675848; b = 1008864; c = 2336716;
			break;
		case 1: a = 1008864; b = 2336716; c = 18025128;
			break;
		case 2: a = 2336716; b = 18025128; c = 17857876;
			break;
		case 3: a = 18025128; b = 17857876; c = 20179076;
			break;
		case 4: a = 17857876; b = 20179076; c = 15778084;
			break;
		case 5: a = 20179076; b = 15778084; c = 6641596;
			break;
		}
	}
	else if (N < 600000) {
		N -= 480000;
		switch (N % 6) {
		case 0: a = 7354432; b = 2126788; c = 11380796;
			break;
		case 1: a = 2126788; b = 11380796; c = 17260348;
			break;
		case 2: a = 11380796; b = 17260348; c = 18564164;
			break;
		case 3: a = 17260348; b = 18564164; c = 19469704;
			break;
		case 4: a = 18564164; b = 19469704; c = 12829780;
			break;
		case 5: a = 19469704; b = 12829780; c = 2157564;
			break;
		}
	}
	else if (N < 720000) {
		N -= 600000;
		switch (N % 6) {
		case 0: a = 16057640; b = 13164080; c = 14574220;
			break;
		case 1: a = 13164080; b = 14574220; c = 633396;
			break;
		case 2: a = 14574220; b = 633396; c = 7384844;
			break;
		case 3: a = 633396; b = 7384844; c = 3497912;
			break;
		case 4: a = 7384844; b = 3497912; c = 8262616;
			break;
		case 5: a = 3497912; b = 8262616; c = 11084812;
			break;
		}
	}
	else if (N < 840000) {
		N -= 720000;
		switch (N % 6) {
		case 0: a = 18595560; b = 11051916; c = 12848552;
			break;
		case 1: a = 11051916; b = 12848552; c = 2257900;
			break;
		case 2: a = 12848552; b = 2257900; c = 6409524;
			break;
		case 3: a = 2257900; b = 6409524; c = 18306044;
			break;
		case 4: a = 6409524; b = 18306044; c = 707672;
			break;
		case 5: a = 18306044; b = 707672; c = 14234392;
			break;
		}
	}
	else {
		N -= 840000;
		switch (N % 6) {
		case 0: a = 4271508; b = 12745376; c = 1551600;
			break;
		case 1: a = 12745376; b = 1551600; c = 11646216;
			break;
		case 2: a = 1551600; b = 11646216; c = 8362968;
			break;
		case 3: a = 11646216; b = 8362968; c = 19829136;
			break;
		case 4: a = 8362968; b = 19829136; c = 2320380;
			break;
		case 5: a = 19829136; b = 2320380; c = 1156588;
			break;
		}
	}
	N /= 6;
	while (N--) {
		a = 2 * (a + c);
		b = 2 * (b + a);
		c = 2 * (c + b);
		a = 2 * (a + c) % 20210108;
		b = 2 * (b + a) % 20210108;
		c = 2 * (c + b) % 20210108;
	}
	std::cout << c;
}