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 <iostream>

using namespace std;
typedef long long ll;

const int hn = 10;
ll a[hn] = { 67867967, 12211937, 23010067, 91744613, 94008721, 40544951, 38567099, 23496587, 23596147, 66666667 };
ll m[hn] = { 69522569, 14921969, 15141163, 92364991, 37171397, 68956417, 66410849, 66612223, 39766409, 64987523 };

ll h[hn][2];
ll ap[hn];

int main() {
	ios_base::sync_with_stdio(0);

	int i; char c;
	cin >> i;

	for (i = 0; i < hn; i++) ap[i] = 1;

	while (true) {
		cin >> c;
		if (cin.eof()) break;

		for (i = 0; i < hn; i++) {
			h[i][0] = (a[i] * h[i][0] + (ll)c) % m[i];
			h[i][1] = (h[i][1] + (ll)c * ap[i]) % m[i];
			ap[i] = (ap[i] * a[i]) % m[i];
		}
	}

	for (i = 0; i < hn; i++) {
		if (h[i][0] != h[i][1]) {
			cout << "NIE" << endl;
			return 0;
		}
	}

	cout << "TAK" << endl;
	return 0;
}