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
49
50
51
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
using namespace std;
ull p_1 = 80003857;
ull q_1 = 1000000009;

ull p_2 = 90434797;
ull q_2 = 1000004897;

ull p_3 = 94126073;
// ull q_3 = 2434245547;

int main(){
	std::ios::sync_with_stdio(false);
	int n;
	cin>>n;
	char c;
	ull act_p1 = 1;
	ull hash_1 = 0;
	ull hashr_1 = 0;
	ull act_p2 = 1;
	ull hash_2 = 0;
	ull hashr_2 = 0;
	ull act_p3 = 1;
	ull hash_3 = 0;
	ull hashr_3 = 0;
	while(cin>>c){
		ull x = (int)c;
		//cout<<x<<endl;
		hash_1 = (hash_1 + act_p1 * x) % q_1;
		act_p1 = (act_p1 * p_1) % q_1;
		hashr_1 = (hashr_1 * p_1) % q_1;
		hashr_1 = (hashr_1 +  x) % q_1;
		hash_2 = (hash_2 + act_p2 * x) % q_2;
		act_p2 = (act_p2 * p_2) % q_2;
		hashr_2 = (hashr_2 * p_2) % q_2;
		hashr_2 = (hashr_2 +  x) % q_2;
		hash_3 = (hash_3 + act_p3 * x); // % q_3;
		act_p3 = (act_p3 * p_3); //% q_3;
		hashr_3 = (hashr_3 * p_3); //% q_3;
		hashr_3 = (hashr_3 +  x); //% q_3;
	}
	//cout<<hash_1<<" "<<hashr_1<<" "<<hash_2<<" "<<hashr_2<<" "<<hash_3<<" "<<hashr_3<<endl;
	if(hash_1 == hashr_1 /*&& hash_2 == hashr_2*/ && hash_3 == hashr_3){
		cout<<"TAK"<<endl;
	}
	else{
		cout<<"NIE"<<endl;
	}
}