#include <iostream>

unsigned long long N, a, b, c;

int main() {
	std::cin >> N;
	switch (N % 24) {
	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;
	}
	N /= 24;
	while (N--) {
		a = 2 * (a + c);
		b = 2 * (b + a);
		c = 2 * (c + b);
		a = 2 * (a + c);
		b = 2 * (b + a);
		c = 2 * (c + b);
		a = 2 * (a + c);
		b = 2 * (b + a);
		c = 2 * (c + b);
		a = 2 * (a + c);
		b = 2 * (b + a);
		c = 2 * (c + b);
		a = 2 * (a + c);
		b = 2 * (b + a);
		c = 2 * (c + b);
		a = 2 * (a + c);
		b = 2 * (b + a);
		c = 2 * (c + b);
		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;
}