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
52
53
54
#include <cstdio>
//https://stackoverflow.com/questions/33333363/built-in-mod-vs-custom-mod-function-improve-the-performance-of-modulus-op/33333636#33333636
inline long long fast_mod(const long long input, const long long ceil) {
    return input >= ceil ? input % ceil : input;
}
struct Hash{
	long long podst;
	long long hash1;
	long long hash2;
	long long hash1wyk;
	long long mod;
	Hash(){}
	Hash(long long podst, long long mod){
			this->podst = podst;
			this->mod = mod;
			this->hash1wyk = 1;
			this->hash1 = 0;
			this->hash2 =0;
	}
	void add(const char & c){
		hash1+=(long long)(c-'a'+1)*hash1wyk;
		hash1 = fast_mod(hash1, mod);
		hash2*=podst;
		hash2 = fast_mod(hash2, mod);
		hash2+=(long long)(c-'a'+1);
		hash2 = fast_mod(hash2, mod);
		hash1wyk *= podst;
		hash1wyk = fast_mod(hash1wyk, mod);
	}
	bool Good(){
		return hash1==hash2;
	}
};

Hash hash;
Hash hash2;
int main(){
	hash = Hash(29,1e9+21);
	hash2 = Hash(31,1e9+696969);
	int a = 1;
	scanf("%d\n",&a);
	char c = getchar_unlocked();
	while(c!=EOF and c!='\n'){
		hash.add(c);
		hash2.add(c);
		c = getchar_unlocked();
	}
	if(!hash.Good() or !hash2.Good()){
		printf("NIE");
		return 0;
	}
	printf("TAK");
	return 0;
}