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
#include <stdio.h>
#include <ctype.h>
using ll = long long;
const ll mod = 1036153287964590673, base = 9423532;
ll mul(ll a, ll b, ll m) {
	ll q = ((long double) a) * b / m;
	ll r = a * b - q * m;
	r %= m;
	if (r < 0)
		r += m;
	return r;
}
int main() {
	scanf("%*d ");
	int c;
	ll h1 = 0, h2 = 0, powe = 1;
	while (!isspace(c = getchar())) {
		h1 = mul(h1, base, mod) + c;
		h2 += mul(powe, c, mod);
		while (h2 > mod)
			h2 -= mod;
		powe = mul(powe, base, mod);
	}
	while (h1 > mod)
		h1 -= mod;
	if (h1 == h2)
		printf("TAK\n");
	else
		printf("NIE\n");
}