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
44
45
46
47
48
#include <cstdio>
#include <cstring>

int primes[] = { 2000000011 , 2000000033, 2000000063, 2000000087, 2000000089, 2000000099, 2000000137, 2000000141 };
int generators[] = {2, 3, 5, 5, 11, 2, 5, 2};
int inverse[] = { 1000000006 , 666666678 , 1200000038, 800000035, 181818190, 1000000050, 800000055 , 1000000071 };
int forward_value[8];
int backward_value[8];
int fpoly_value[8];
int bpoly_value[8];

int n;
const int buffer_size = 4096;
char buffer[buffer_size + 1];


int main() {
	scanf("%d\n", &n);
	buffer[buffer_size] = 0;
	for (int j = 0; j < 8; ++j) {
		forward_value[j] = 0;
		backward_value[j] = 0;
		fpoly_value[j] = generators[j];
		bpoly_value[j] = inverse[j];
	}
	while (fgets(buffer, buffer_size, stdin)) {
		n = strlen(buffer);
		for (int i = 0; i < n; ++i) {
			if (buffer[i] < 'a' || buffer[i] > 'z') break;
			int c = buffer[i] - 'a';
			for (int j = 0; j < 8; ++j) {
				forward_value[j] = (forward_value[j] + (long long)(c)* fpoly_value[j]) % primes[j];
				backward_value[j] = (backward_value[j] + (long long)(c)* bpoly_value[j]) % primes[j];
				fpoly_value[j] = ((long long)(generators[j])* fpoly_value[j]) % primes[j];
				bpoly_value[j] = ((long long)(inverse[j])* bpoly_value[j]) % primes[j];
			}
		}
	}
	bool match = true;
	for (int j = 0; j < 8; ++j) {
		if (forward_value[j] != ((long long)(backward_value[j]) * fpoly_value[j]) % primes[j]) {
			match = false;
			break;
		}
	}
	printf("%s", match ? "TAK" : "NIE");
	return 0;
}