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
#include <bits/stdc++.h>

const int Q = 10007;
const int MX = 1e9 + 7;
const int MOD = 1234567891;

int main(){
	int cur[2] = {1, 1};
	int haszL[2] = {0, 0};
	int haszR[2] = {0, 0};
	
	int n;
	scanf("%d", &n);
	
	char t = ' ';
	while(t < 'a' || 'z' < t)
		t = getchar();
	
	while('a' <= t && t <= 'z'){
		haszL[0] = (1LL * haszL[0] * Q + t)%MX;
		haszL[1] = (1LL * haszL[1] * Q + t)%MOD;
		
		haszR[0] = (1LL * cur[0] * t + haszR[0])%MX;
		haszR[1] = (1LL * cur[1] * t + haszR[1])%MOD;
		
		cur[0] = (1LL * Q * cur[0])%MX;
		cur[1] = (1LL * Q * cur[1])%MOD;
		t = getchar();
	}
	
	if(haszL[0] == haszR[0] && haszL[1] == haszR[1])
		puts("TAK");
	else
		puts("NIE");
	return 0;
}