!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

int n, m = 99999999;
scanf("%d", &n);
long long a1 = 2, a2 = 3;
long long b1 = 1, b2 = 4;
long long c1 = 6, c2 = 5;
long long d1, d2;
if (n == 1) {
	printf("%lld\n%lld\n", a1 % m, a2 % m);
} else if (n == 2) {
	printf("%lld\n%lld\n", b1 % m, b2 % m);
} else if (n == 3) {
	printf("%lld\n%lld\n", c1 % m, c2 % m);
} else {
	for (int i = 4; i <= n; i++) {
		d1 = (c2 + 2 * a1 + 5) % m;
		d2 = (c1 + 3 * a1 + 2 * a2 + 3) % m;
		a1 = b1;
		a2 = b2;
		b1 = c1;
		b2 = c2;
		c1 = d1;
		c2 = d2;
	}
	printf("%lld\n%lld\n", c1, c2);
}
return 0;

}