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
#include<cstdio>
#include<iostream>
using namespace std;

int n;
char c;
const int hashesCount = 2;

unsigned long long int modulos[4] = {300000000000000011ULL, 300000000000000017ULL, 300000000000000029ULL, 300000000000000049ULL};
unsigned long long int frontHash[4] = {0, 0, 0, 0};
unsigned long long int backHash[4] = {0, 0, 0, 0};
unsigned long long int frontBase[4] = {1, 1, 1, 1};

unsigned long long int hashBase = 30;

bool myIsAlpha(char x){
    return x >= 'a' && x <= 'z';
}

int main(){
	scanf("%d", &n);
    c=getchar();
	while(myIsAlpha(c=getchar())){
		for(int i = 0; i < hashesCount; ++i){
			backHash[i] = (backHash[i] * hashBase + c - 'a') % modulos[i];			
			frontHash[i] = (frontHash[i] + frontBase[i] * (c - 'a')) % modulos[i];			
			frontBase[i] = (frontBase[i] * hashBase) % modulos[i];
		}
	}
	
	for (int i = 0; i < hashesCount; ++i){
		if(frontHash[i] != backHash[i]){
			printf("NIE\n");
			return 0;
		}
	}
	printf("TAK\n");
	
	return 0;
}