#include <iostream>

unsigned int N, a, b, c;

int main() {
	std::cin >> N;
	switch (N % 6) {
	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;
	}
	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;
	}
	std::cout << c;
}