#include <iostream>

unsigned int N;
unsigned long long a, b, c;

int main() {
	std::cin >> N;
	switch (N % 33) {
	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;
	case 6: a = 24; b = 56; c = 132; break;
	case 7: a = 56; b = 132; c = 312; break;
	case 8: a = 132; b = 312; c = 736; break;
	case 9: a = 312; b = 736; c = 1736; break;
	case 10: a = 736; b = 1736; c = 4096; break;
	case 11: a = 1736; b = 4096; c = 9664; break;
	case 12: a = 4096; b = 9664; c = 22800; break;
	case 13: a = 9664; b = 22800; c = 53792; break;
	case 14: a = 22800; b = 53792; c = 126912; break;
	case 15: a = 53792; b = 126912; c = 299424; break;
	case 16: a = 126912; b = 299424; c = 706432; break;
	case 17: a = 299424; b = 706432; c = 1666688; break;
	case 18: a = 706432; b = 1666688; c = 3932224; break;
	case 19: a = 1666688; b = 3932224; c = 9277312; break;
	case 20: a = 3932224; b = 9277312; c = 1677892; break;
	case 21: a = 9277312; b = 1677892; c = 11220232; break;
	case 22: a = 1677892; b = 11220232; c = 574872; break;
	case 23: a = 11220232; b = 574872; c = 4505528; break;
	case 24: a = 574872; b = 4505528; c = 11241412; break;
	case 25: a = 4505528; b = 11241412; c = 3422460; break;
	case 26: a = 11241412; b = 3422460; c = 15855976; break;
	case 27: a = 3422460; b = 15855976; c = 13774560; break;
	case 28: a = 15855976; b = 13774560; c = 14183932; break;
	case 29: a = 13774560; b = 14183932; c = 19659600; break;
	case 30: a = 14183932; b = 19659600; c = 6237996; break;
	case 31: a = 19659600; b = 6237996; c = 423640; break;
	case 32: a = 6237996; b = 423640; c = 19956372; break;
	}
	N /= 33;
	while (N--) {
		a += c;
		b += a << 1;
		c += b << 1;
		a += c;
		b += a << 1;
		c += b << 1;
		a += c;
		b += a << 1;
		c += b << 1;
		a += c;
		b += a << 1;
		c += b << 1;
		a += c;
		b += a << 1;
		c += b << 1;
		a += c;
		b += a << 1;
		c += b << 1;
		a += c;
		b += a << 1;
		c += b << 1;
		a += c;
		b += a << 1;
		c += b << 1;
		a += c;
		b += a << 1;
		c += b << 1;
		a += c;
		b += a << 1;
		c += b << 1;
		a = ((a + c) << 11) % 20210108;
		b = ((b << 11) + (a << 1)) % 20210108;
		c = ((c << 11) + (b << 1)) % 20210108;
	}
	std::cout << c;
}