1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <cstdio>
#include <utility>
#include <cctype>

using namespace std;

constexpr int PS = 5;

pair<long long, long long> primes[PS] = {
	{1542457099, 1542457417},
	{1342456501, 1342462799},
	{1342466809, 1842466739},
	{1842457277, 1942457677},
	{1942465691, 1952467277}
};
long long p[PS] = {1, 1, 1, 1, 1}, hash_forward[PS], hash_backward[PS];

int main() {
	int n;
	char c;
	scanf("%d", &n);
	while(isspace(c = getchar()));
	
	do {
		for (int j = 0; j < PS; j++) {
			hash_forward[j] = (hash_forward[j] + c * p[j]) % primes[j].second;
			hash_backward[j] = (hash_backward[j] * primes[j].first + c) % primes[j].second;
			p[j] = (p[j] * primes[j].first) % primes[j].second;
		}
		c = getchar();
	} while (c != EOF && !isspace(c));

	for (int i = 0; i < PS; i++) {
		if (hash_forward[i] != hash_backward[i]) {
			printf("NIE\n");
			return 0;
		}
	}

	printf("TAK\n");
}