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
42
43
#include<cstdio>
typedef unsigned long long u64;

const u64 inv = 9150747060186627967LLU;
const u64 prime = 127;

u64 H, Hinv, m = prime, minv;
char c; int n;

int len = 0, base = 20000100;

u64 fexp(u64 base, u64 exp) {
	u64 m = base, res = 1;
	while(exp > 0) {
		if(exp & 1)res *= m;
		m = m*m;
		exp >>= 1;
	}	
	return res;
}

int main(){
	scanf("%*d\n");
	minv = fexp(prime, base);

	while(true) {
		int ret = scanf("%c", &c);
		if(ret == -1 || c == '\n')
			break;
		len++;
		H += m*(c - 'a' + 7);
		Hinv += minv * (c - 'a' + 7);

		m *= prime;
		minv *= inv;
	}

	H *= fexp(prime, base - len);

	printf("%s\n", H == Hinv ? "TAK" : "NIE");

	return 0;
}