#include <stdio.h>

unsigned int N, a, b, c;

int main() {
	scanf("%d", &N);
	if (N < 30000) {
		int rb[][3] = {
			{ 0, 1, 0 },
			{ 1, 2, 0 },
			{ 1, 2, 4 },
			{ 2, 4, 10 },
			{ 4, 10, 24 },
			{ 10, 24, 56 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else if (N < 60000) {
		int rb[][3] = {
			{ 15299844, 3673692, 4123372 },
			{ 3673692, 4123372, 18636324 },
			{ 4123372, 18636324, 4199816 },
			{ 18636324, 4199816, 16646376 },
			{ 4199816, 16646376, 9935076 },
			{ 16646376, 9935076, 8059676 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else if (N < 90000) {
		int rb[][3] = {
			{ 7293784, 9752240, 7091580 },
			{ 9752240, 7091580, 8560620 },
			{ 7091580, 8560620, 16415612 },
			{ 8560620, 16415612, 6594168 },
			{ 16415612, 6594168, 10099468 },
			{ 6594168, 10099468, 12609944 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else if (N < 120000) {
		int rb[][3] = {
			{ 8811896, 3891300, 2119360 },
			{ 3891300, 2119360, 1652404 },
			{ 2119360, 1652404, 11087408 },
			{ 1652404, 11087408, 6203428 },
			{ 11087408, 6203428, 15711664 },
			{ 6203428, 15711664, 13177928 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else if (N < 150000) {
		int rb[][3] = {
			{ 19850648, 9089956, 13284784 },
			{ 9089956, 13284784, 5640540 },
			{ 13284784, 5640540, 9250884 },
			{ 5640540, 9250884, 4651120 },
			{ 9250884, 4651120, 373212 },
			{ 4651120, 373212, 19248192 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else if (N < 180000) {
		int rb[][3] = {
			{ 11163620, 19644740, 10695996 },
			{ 19644740, 10695996, 3299016 },
			{ 10695996, 3299016, 5467296 },
			{ 3299016, 5467296, 12116476 },
			{ 5467296, 12116476, 10620876 },
			{ 12116476, 10620876, 11966236 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else if (N < 210000) {
		int rb[][3] = {
			{ 10604864, 11402808, 4677708 },
			{ 11402808, 4677708, 10355036 },
			{ 4677708, 10355036, 3095472 },
			{ 10355036, 3095472, 15546360 },
			{ 3095472, 15546360, 11382576 },
			{ 15546360, 11382576, 8745988 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else if (N < 240000) {
		int rb[][3] = {
			{ 3579656, 19276332, 13613652 },
			{ 19276332, 13613652, 14176508 },
			{ 13613652, 14176508, 6275356 },
			{ 14176508, 6275356, 19567908 },
			{ 6275356, 19567908, 6858508 },
			{ 19567908, 6858508, 6057620 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else if (N < 270000) {
		int rb[][3] = {
			{ 10698836, 10716036, 5181544 },
			{ 10716036, 5181544, 11550652 },
			{ 5181544, 11550652, 4113160 },
			{ 11550652, 4113160, 18589408 },
			{ 4113160, 18589408, 19859904 },
			{ 18589408, 19859904, 7525912 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else if (N < 300000) {
		int rb[][3] = {
			{ 12247020, 16689160, 16100500 },
			{ 16689160, 16100500, 16274824 },
			{ 16100500, 16274824, 5297644 },
			{ 16274824, 5297644, 2376072 },
			{ 5297644, 2376072, 17091684 },
			{ 2376072, 17091684, 4358440 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else if (N < 330000) {
		int rb[][3] = {
			{ 3256344, 16459384, 12334896 },
			{ 16459384, 12334896, 10972372 },
			{ 12334896, 10972372, 14443296 },
			{ 10972372, 14443296, 13136168 },
			{ 14443296, 13136168, 7796864 },
			{ 13136168, 7796864, 4060104 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else if (N < 360000) {
		int rb[][3] = {
			{ 16616728, 16827648, 11658332 },
			{ 16827648, 11658332, 16129904 },
			{ 11658332, 16129904, 5284780 },
			{ 16129904, 5284780, 13676116 },
			{ 5284780, 13676116, 19191824 },
			{ 13676116, 19191824, 8532992 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else if (N < 390000) {
		int rb[][3] = {
			{ 6675848, 1008864, 2336716 },
			{ 1008864, 2336716, 18025128 },
			{ 2336716, 18025128, 17857876 },
			{ 18025128, 17857876, 20179076 },
			{ 17857876, 20179076, 15778084 },
			{ 20179076, 15778084, 6641596 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else if (N < 420000) {
		int rb[][3] = {
			{ 16421412, 288428, 10247200 },
			{ 288428, 10247200, 12917008 },
			{ 10247200, 12917008, 6200764 },
			{ 12917008, 6200764, 12685820 },
			{ 6200764, 12685820, 10785440 },
			{ 12685820, 10785440, 13762300 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else if (N < 450000) {
		int rb[][3] = {
			{ 3754772, 8231096, 13906628 },
			{ 8231096, 13906628, 15112692 },
			{ 13906628, 15112692, 6267360 },
			{ 15112692, 6267360, 20137868 },
			{ 6267360, 20137868, 9870796 },
			{ 20137868, 9870796, 12066204 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else if (N < 480000) {
		int rb[][3] = {
			{ 4192024, 17562704, 18377720 },
			{ 17562704, 18377720, 4719272 },
			{ 18377720, 4719272, 4143736 },
			{ 4719272, 4143736, 4622696 },
			{ 4143736, 4622696, 18683936 },
			{ 4622696, 18683936, 5235128 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else if (N < 510000) {
		int rb[][3] = {
			{ 7354432, 2126788, 11380796 },
			{ 2126788, 11380796, 17260348 },
			{ 11380796, 17260348, 18564164 },
			{ 17260348, 18564164, 19469704 },
			{ 18564164, 19469704, 12829780 },
			{ 19469704, 12829780, 2157564 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else if (N < 540000) {
		int rb[][3] = {
			{ 145248, 6869852, 16346176 },
			{ 6869852, 16346176, 12772740 },
			{ 16346176, 12772740, 19075076 },
			{ 12772740, 19075076, 10212180 },
			{ 19075076, 10212180, 5549624 },
			{ 10212180, 5549624, 8829184 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else if (N < 570000) {
		int rb[][3] = {
			{ 978792, 8392444, 16305132 },
			{ 8392444, 16305132, 14357740 },
			{ 16305132, 14357740, 5080152 },
			{ 14357740, 5080152, 2350352 },
			{ 5080152, 2350352, 13206076 },
			{ 2350352, 13206076, 16362348 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else if (N < 600000) {
		int rb[][3] = {
			{ 14602080, 10779672, 6976576 },
			{ 10779672, 6976576, 2737096 },
			{ 6976576, 2737096, 6823428 },
			{ 2737096, 6823428, 7389900 },
			{ 6823428, 7389900, 43884 },
			{ 7389900, 43884, 13734624 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else if (N < 630000) {
		int rb[][3] = {
			{ 16057640, 13164080, 14574220 },
			{ 13164080, 14574220, 633396 },
			{ 14574220, 633396, 7384844 },
			{ 633396, 7384844, 3497912 },
			{ 7384844, 3497912, 8262616 },
			{ 3497912, 8262616, 11084812 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else if (N < 660000) {
		int rb[][3] = {
			{ 7809792, 3297736, 4957744 },
			{ 3297736, 4957744, 5324964 },
			{ 4957744, 5324964, 17245400 },
			{ 5324964, 17245400, 3986072 },
			{ 17245400, 3986072, 18622072 },
			{ 3986072, 18622072, 11104620 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else if (N < 690000) {
		int rb[][3] = {
			{ 13174648, 15404832, 6304484 },
			{ 15404832, 6304484, 18748156 },
			{ 6304484, 18748156, 7675652 },
			{ 18748156, 7675652, 7750164 },
			{ 7675652, 7750164, 12576424 },
			{ 7750164, 12576424, 83936 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else if (N < 720000) {
		int rb[][3] = {
			{ 457956, 15881308, 8976 },
			{ 15881308, 8976, 933864 },
			{ 8976, 933864, 13420236 },
			{ 933864, 13420236, 6648316 },
			{ 13420236, 6648316, 15164360 },
			{ 6648316, 15164360, 16748976 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else if (N < 750000) {
		int rb[][3] = {
			{ 18595560, 11051916, 12848552 },
			{ 11051916, 12848552, 2257900 },
			{ 12848552, 2257900, 6409524 },
			{ 2257900, 6409524, 18306044 },
			{ 6409524, 18306044, 707672 },
			{ 18306044, 707672, 14234392 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else if (N < 780000) {
		int rb[][3] = {
			{ 7753632, 2818556, 5211004 },
			{ 2818556, 5211004, 5719164 },
			{ 5211004, 5719164, 17075440 },
			{ 5719164, 17075440, 4152672 },
			{ 17075440, 4152672, 19743672 },
			{ 4152672, 19743672, 13007900 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else if (N < 810000) {
		int rb[][3] = {
			{ 9320488, 10318556, 13916220 },
			{ 10318556, 13916220, 6053200 },
			{ 13916220, 6053200, 12533404 },
			{ 6053200, 12533404, 12479032 },
			{ 12533404, 12479032, 16854356 },
			{ 12479032, 16854356, 18355304 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else if (N < 840000) {
		int rb[][3] = {
			{ 5960624, 6960772, 17368660 },
			{ 6960772, 17368660, 6238352 },
			{ 17368660, 6238352, 6188140 },
			{ 6238352, 6188140, 6693384 },
			{ 6188140, 6693384, 5653364 },
			{ 6693384, 5653364, 3472900 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else if (N < 870000) {
		int rb[][3] = {
			{ 4271508, 12745376, 1551600 },
			{ 12745376, 1551600, 11646216 },
			{ 1551600, 11646216, 8362968 },
			{ 11646216, 8362968, 19829136 },
			{ 8362968, 19829136, 2320380 },
			{ 19829136, 2320380, 1156588 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else if (N < 900000) {
		int rb[][3] = {
			{ 16935592, 8304596, 12840200 },
			{ 8304596, 12840200, 19131368 },
			{ 12840200, 19131368, 14451712 },
			{ 19131368, 14451712, 14163608 },
			{ 14451712, 14163608, 5959628 },
			{ 14163608, 5959628, 402464 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else if (N < 930000) {
		int rb[][3] = {
			{ 7444204, 14920928, 1281232 },
			{ 14920928, 1281232, 17450872 },
			{ 1281232, 17450872, 4113276 },
			{ 17450872, 4113276, 10789016 },
			{ 4113276, 10789016, 16059560 },
			{ 10789016, 16059560, 20135564 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else if (N < 960000) {
		int rb[][3] = {
			{ 16671040, 8399084, 11013720 },
			{ 8399084, 11013720, 14949304 },
			{ 11013720, 14949304, 6276560 },
			{ 14949304, 6276560, 14370452 },
			{ 6276560, 14370452, 18219296 },
			{ 14370452, 18219296, 8571496 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else if (N < 990000) {
		int rb[][3] = {
			{ 6268968, 14735608, 8600960 },
			{ 14735608, 8600960, 9529748 },
			{ 8600960, 9529748, 8110496 },
			{ 9529748, 8110496, 13212804 },
			{ 8110496, 13212804, 5064888 },
			{ 13212804, 5064888, 6140660 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	} else {
		int rb[][3] = {
			{ 10733100, 10385976, 15062948 },
			{ 10385976, 15062948, 11171880 },
			{ 15062948, 11171880, 2695496 },
			{ 11171880, 2695496, 15306780 },
			{ 2695496, 15306780, 12537104 },
			{ 15306780, 12537104, 10255092 }
		};
		int m = N % 6;
		a = rb[m][0];
		b = rb[m][1];
		c = rb[m][2];
	}
	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;
	}
	printf("%d", c);
}