5792021-11-03 21:10:07Kris030Toronyépítés (1,1,3,3)cpp11Accepted 50/502ms1272 KiB
#include <stdio.h>

unsigned int N, a, b, c;

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

int main() {
	scanf("%d", &N);
	int k = N / 30000, j = N % 6;

	a = table[k][j][0];
	b = table[k][j][1];
	c = table[k][j][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);
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/02ms1252 KiB
2Accepted0/01ms1272 KiB
3Accepted3/31ms1224 KiB
4Accepted3/31ms1164 KiB
5Accepted4/41ms1168 KiB
6Accepted4/41ms1168 KiB
7Accepted4/41ms1172 KiB
8Accepted4/41ms1112 KiB
9Accepted4/41ms1180 KiB
10Accepted4/41ms1252 KiB
11Accepted4/41ms1188 KiB
12Accepted4/41ms1192 KiB
13Accepted4/41ms1264 KiB
14Accepted4/41ms1196 KiB
15Accepted2/21ms1204 KiB
16Accepted2/21ms1208 KiB