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
#include<cstdio>
#define mod1 1000000009
#define mod2 1000696969
#define mno1 31
#define mno2 29

long long h1_L,h2_L,h1_R,h2_R,n;
char c;

long long potmod(long long a,long long pow,long long mod)
{
	if(pow==0)return 1;
	if(pow&1)return (potmod(a,pow-1,mod)*a)%mod;
	else 
	{
		long long x=potmod(a,pow/2,mod);
		return (x*x)%mod;
	}
}

int main()
{
	scanf("%lld\n",&n);
	int i;
	while(1)
	{
		scanf("%c",&c);
		if(c=='\n')break;
		c-='a';
		h1_L=(h1_L*mno1+c)%mod1;
		h2_L=(h2_L*mno2+c)%mod2;
		h1_R=(h1_R+c*potmod(mno1,i,mod1))%mod1;
		h2_R=(h2_R+c*potmod(mno2,i,mod2))%mod2;
		i++;
	}
	if(h1_L==h1_R&&h2_L==h2_R)printf("TAK");
	else printf("NIE");
}