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

#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef vector < int > VI;
typedef double D;

const int MN = 100005, inf = 1000000005, mod = 1000000007;
const LL INF = 1000000000000000005LL;

const LL p = 7907LL, q = 1951LL, r = 99999929LL, s = 1771907789LL;


int main()
{
	int n;
	scanf("%d", &n);
	char cur;
	LL P = 1LL, Q = 1LL, prefP = 0LL, prefQ = 0LL, sufP = 0LL, sufQ = 0LL, X = 1LL, prefX = 0LL, sufX = 0LL;
	while(scanf("%c", &cur) != -1)
	{
		if(cur < 'a' || cur > 'z')
			continue;
		//cout << "literka to : "<< cur << " <- wyglada ok?" << endl;
		LL c = cur - 'a' + 1;
		prefP = (prefP * p + c) % r;
		sufP = (sufP + P * c) % r;
		prefQ = (prefQ * q + c) % s;
		sufQ= (sufQ + Q * c) % s;
		//prefX = (prefX * p + c) % s;
		//sufX = (sufX + X * c) % s;
		P = (P * p) % r;
		Q = (Q * q) % s;
		//X = (X * p) % s;
	}
	//printf("%lld %lld %lld %lld %lld %lld\n", prefX, sufX, prefP, sufP, prefQ, sufQ);
	if((prefP != sufP) || (prefQ != sufQ) || (prefX != sufX))
		printf("NIE");
	else
		printf("TAK");
}