#include <stdio.h>
unsigned int N, a, b, c;
int main() {
scanf("%d", &N);
unsigned int* t = ((unsigned int[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 }
}
})[N / 30000][N % 6];
a = t[0];
b = t[1];
c = t[2];
N = (N % 30000) / 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);
}