#include <iostream>

unsigned int N, a, b, c;

int main() {
	std::cin >> N;
	if (N < 30000) {
		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 < 60000) {
		switch (N % 6) {
		case 0: a = 15299844; b = 3673692; c = 4123372; break;
		case 1: a = 3673692; b = 4123372; c = 18636324; break;
		case 2: a = 4123372; b = 18636324; c = 4199816; break;
		case 3: a = 18636324; b = 4199816; c = 16646376; break;
		case 4: a = 4199816; b = 16646376; c = 9935076; break;
		case 5: a = 16646376; b = 9935076; c = 8059676; break;
		}
	}
	else if (N < 90000) {
		switch (N % 6) {
		case 0: a = 7293784; b = 9752240; c = 7091580; break;
		case 1: a = 9752240; b = 7091580; c = 8560620; break;
		case 2: a = 7091580; b = 8560620; c = 16415612; break;
		case 3: a = 8560620; b = 16415612; c = 6594168; break;
		case 4: a = 16415612; b = 6594168; c = 10099468; break;
		case 5: a = 6594168; b = 10099468; c = 12609944; break;
		}
	}
	else if (N < 120000) {
		switch (N % 6) {
		case 0: a = 8811896; b = 3891300; c = 2119360; break;
		case 1: a = 3891300; b = 2119360; c = 1652404; break;
		case 2: a = 2119360; b = 1652404; c = 11087408; break;
		case 3: a = 1652404; b = 11087408; c = 6203428; break;
		case 4: a = 11087408; b = 6203428; c = 15711664; break;
		case 5: a = 6203428; b = 15711664; c = 13177928; break;
		}
	}
	else if (N < 150000) {
		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 < 180000) {
		switch (N % 6) {
		case 0: a = 11163620; b = 19644740; c = 10695996; break;
		case 1: a = 19644740; b = 10695996; c = 3299016; break;
		case 2: a = 10695996; b = 3299016; c = 5467296; break;
		case 3: a = 3299016; b = 5467296; c = 12116476; break;
		case 4: a = 5467296; b = 12116476; c = 10620876; break;
		case 5: a = 12116476; b = 10620876; c = 11966236; break;
		}
	}
	else if (N < 210000) {
		switch (N % 6) {
		case 0: a = 10604864; b = 11402808; c = 4677708; break;
		case 1: a = 11402808; b = 4677708; c = 10355036; break;
		case 2: a = 4677708; b = 10355036; c = 3095472; break;
		case 3: a = 10355036; b = 3095472; c = 15546360; break;
		case 4: a = 3095472; b = 15546360; c = 11382576; break;
		case 5: a = 15546360; b = 11382576; c = 8745988; break;
		}
	}
	else if (N < 240000) {
		switch (N % 6) {
		case 0: a = 3579656; b = 19276332; c = 13613652; break;
		case 1: a = 19276332; b = 13613652; c = 14176508; break;
		case 2: a = 13613652; b = 14176508; c = 6275356; break;
		case 3: a = 14176508; b = 6275356; c = 19567908; break;
		case 4: a = 6275356; b = 19567908; c = 6858508; break;
		case 5: a = 19567908; b = 6858508; c = 6057620; break;
		}
	}
	else if (N < 270000) {
		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 < 300000) {
		switch (N % 6) {
		case 0: a = 12247020; b = 16689160; c = 16100500; break;
		case 1: a = 16689160; b = 16100500; c = 16274824; break;
		case 2: a = 16100500; b = 16274824; c = 5297644; break;
		case 3: a = 16274824; b = 5297644; c = 2376072; break;
		case 4: a = 5297644; b = 2376072; c = 17091684; break;
		case 5: a = 2376072; b = 17091684; c = 4358440; break;
		}
	}
	else if (N < 330000) {
		switch (N % 6) {
		case 0: a = 3256344; b = 16459384; c = 12334896; break;
		case 1: a = 16459384; b = 12334896; c = 10972372; break;
		case 2: a = 12334896; b = 10972372; c = 14443296; break;
		case 3: a = 10972372; b = 14443296; c = 13136168; break;
		case 4: a = 14443296; b = 13136168; c = 7796864; break;
		case 5: a = 13136168; b = 7796864; c = 4060104; break;
		}
	}
	else if (N < 360000) {
		switch (N % 6) {
		case 0: a = 16616728; b = 16827648; c = 11658332; break;
		case 1: a = 16827648; b = 11658332; c = 16129904; break;
		case 2: a = 11658332; b = 16129904; c = 5284780; break;
		case 3: a = 16129904; b = 5284780; c = 13676116; break;
		case 4: a = 5284780; b = 13676116; c = 19191824; break;
		case 5: a = 13676116; b = 19191824; c = 8532992; break;
		}
	}
	else if (N < 390000) {
		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 < 420000) {
		switch (N % 6) {
		case 0: a = 16421412; b = 288428; c = 10247200; break;
		case 1: a = 288428; b = 10247200; c = 12917008; break;
		case 2: a = 10247200; b = 12917008; c = 6200764; break;
		case 3: a = 12917008; b = 6200764; c = 12685820; break;
		case 4: a = 6200764; b = 12685820; c = 10785440; break;
		case 5: a = 12685820; b = 10785440; c = 13762300; break;
		}
	}
	else if (N < 450000) {
		switch (N % 6) {
		case 0: a = 3754772; b = 8231096; c = 13906628; break;
		case 1: a = 8231096; b = 13906628; c = 15112692; break;
		case 2: a = 13906628; b = 15112692; c = 6267360; break;
		case 3: a = 15112692; b = 6267360; c = 20137868; break;
		case 4: a = 6267360; b = 20137868; c = 9870796; break;
		case 5: a = 20137868; b = 9870796; c = 12066204; break;
		}
	}
	else if (N < 480000) {
		switch (N % 6) {
		case 0: a = 4192024; b = 17562704; c = 18377720; break;
		case 1: a = 17562704; b = 18377720; c = 4719272; break;
		case 2: a = 18377720; b = 4719272; c = 4143736; break;
		case 3: a = 4719272; b = 4143736; c = 4622696; break;
		case 4: a = 4143736; b = 4622696; c = 18683936; break;
		case 5: a = 4622696; b = 18683936; c = 5235128; break;
		}
	}
	else if (N < 510000) {
		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 < 540000) {
		switch (N % 6) {
		case 0: a = 145248; b = 6869852; c = 16346176; break;
		case 1: a = 6869852; b = 16346176; c = 12772740; break;
		case 2: a = 16346176; b = 12772740; c = 19075076; break;
		case 3: a = 12772740; b = 19075076; c = 10212180; break;
		case 4: a = 19075076; b = 10212180; c = 5549624; break;
		case 5: a = 10212180; b = 5549624; c = 8829184; break;
		}
	}
	else if (N < 570000) {
		switch (N % 6) {
		case 0: a = 978792; b = 8392444; c = 16305132; break;
		case 1: a = 8392444; b = 16305132; c = 14357740; break;
		case 2: a = 16305132; b = 14357740; c = 5080152; break;
		case 3: a = 14357740; b = 5080152; c = 2350352; break;
		case 4: a = 5080152; b = 2350352; c = 13206076; break;
		case 5: a = 2350352; b = 13206076; c = 16362348; break;
		}
	}
	else if (N < 600000) {
		switch (N % 6) {
		case 0: a = 14602080; b = 10779672; c = 6976576; break;
		case 1: a = 10779672; b = 6976576; c = 2737096; break;
		case 2: a = 6976576; b = 2737096; c = 6823428; break;
		case 3: a = 2737096; b = 6823428; c = 7389900; break;
		case 4: a = 6823428; b = 7389900; c = 43884; break;
		case 5: a = 7389900; b = 43884; c = 13734624; break;
		}
	}
	else if (N < 630000) {
		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 < 660000) {
		switch (N % 6) {
		case 0: a = 7809792; b = 3297736; c = 4957744; break;
		case 1: a = 3297736; b = 4957744; c = 5324964; break;
		case 2: a = 4957744; b = 5324964; c = 17245400; break;
		case 3: a = 5324964; b = 17245400; c = 3986072; break;
		case 4: a = 17245400; b = 3986072; c = 18622072; break;
		case 5: a = 3986072; b = 18622072; c = 11104620; break;
		}
	}
	else if (N < 690000) {
		switch (N % 6) {
		case 0: a = 13174648; b = 15404832; c = 6304484; break;
		case 1: a = 15404832; b = 6304484; c = 18748156; break;
		case 2: a = 6304484; b = 18748156; c = 7675652; break;
		case 3: a = 18748156; b = 7675652; c = 7750164; break;
		case 4: a = 7675652; b = 7750164; c = 12576424; break;
		case 5: a = 7750164; b = 12576424; c = 83936; break;
		}
	}
	else if (N < 720000) {
		switch (N % 6) {
		case 0: a = 457956; b = 15881308; c = 8976; break;
		case 1: a = 15881308; b = 8976; c = 933864; break;
		case 2: a = 8976; b = 933864; c = 13420236; break;
		case 3: a = 933864; b = 13420236; c = 6648316; break;
		case 4: a = 13420236; b = 6648316; c = 15164360; break;
		case 5: a = 6648316; b = 15164360; c = 16748976; break;
		}
	}
	else if (N < 750000) {
		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 if (N < 780000) {
		switch (N % 6) {
		case 0: a = 7753632; b = 2818556; c = 5211004; break;
		case 1: a = 2818556; b = 5211004; c = 5719164; break;
		case 2: a = 5211004; b = 5719164; c = 17075440; break;
		case 3: a = 5719164; b = 17075440; c = 4152672; break;
		case 4: a = 17075440; b = 4152672; c = 19743672; break;
		case 5: a = 4152672; b = 19743672; c = 13007900; break;
		}
	}
	else if (N < 810000) {
		switch (N % 6) {
		case 0: a = 9320488; b = 10318556; c = 13916220; break;
		case 1: a = 10318556; b = 13916220; c = 6053200; break;
		case 2: a = 13916220; b = 6053200; c = 12533404; break;
		case 3: a = 6053200; b = 12533404; c = 12479032; break;
		case 4: a = 12533404; b = 12479032; c = 16854356; break;
		case 5: a = 12479032; b = 16854356; c = 18355304; break;
		}
	}
	else if (N < 840000) {
		switch (N % 6) {
		case 0: a = 5960624; b = 6960772; c = 17368660; break;
		case 1: a = 6960772; b = 17368660; c = 6238352; break;
		case 2: a = 17368660; b = 6238352; c = 6188140; break;
		case 3: a = 6238352; b = 6188140; c = 6693384; break;
		case 4: a = 6188140; b = 6693384; c = 5653364; break;
		case 5: a = 6693384; b = 5653364; c = 3472900; break;
		}
	}
	else if (N < 870000) {
		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;
		}
	}
	else if (N < 900000) {
		switch (N % 6) {
		case 0: a = 16935592; b = 8304596; c = 12840200; break;
		case 1: a = 8304596; b = 12840200; c = 19131368; break;
		case 2: a = 12840200; b = 19131368; c = 14451712; break;
		case 3: a = 19131368; b = 14451712; c = 14163608; break;
		case 4: a = 14451712; b = 14163608; c = 5959628; break;
		case 5: a = 14163608; b = 5959628; c = 402464; break;
		}
	}
	else if (N < 930000) {
		switch (N % 6) {
		case 0: a = 7444204; b = 14920928; c = 1281232; break;
		case 1: a = 14920928; b = 1281232; c = 17450872; break;
		case 2: a = 1281232; b = 17450872; c = 4113276; break;
		case 3: a = 17450872; b = 4113276; c = 10789016; break;
		case 4: a = 4113276; b = 10789016; c = 16059560; break;
		case 5: a = 10789016; b = 16059560; c = 20135564; break;
		}
	}
	else if (N < 960000) {
		switch (N % 6) {
		case 0: a = 16671040; b = 8399084; c = 11013720; break;
		case 1: a = 8399084; b = 11013720; c = 14949304; break;
		case 2: a = 11013720; b = 14949304; c = 6276560; break;
		case 3: a = 14949304; b = 6276560; c = 14370452; break;
		case 4: a = 6276560; b = 14370452; c = 18219296; break;
		case 5: a = 14370452; b = 18219296; c = 8571496; break;
		}
	}
	else if (N < 990000) {
		switch (N % 6) {
		case 0: a = 6268968; b = 14735608; c = 8600960; break;
		case 1: a = 14735608; b = 8600960; c = 9529748; break;
		case 2: a = 8600960; b = 9529748; c = 8110496; break;
		case 3: a = 9529748; b = 8110496; c = 13212804; break;
		case 4: a = 8110496; b = 13212804; c = 5064888; break;
		case 5: a = 13212804; b = 5064888; c = 6140660; break;
		}
	}
	else {
		switch (N % 6) {
		case 0: a = 10733100; b = 10385976; c = 15062948; break;
		case 1: a = 10385976; b = 15062948; c = 11171880; break;
		case 2: a = 15062948; b = 11171880; c = 2695496; break;
		case 3: a = 11171880; b = 2695496; c = 15306780; break;
		case 4: a = 2695496; b = 15306780; c = 12537104; break;
		case 5: a = 15306780; b = 12537104; c = 10255092; break;
		}
	}
	N %= 30000;
	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;
}