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
55
56
57
58
59
60
#define _CRT_SECURE_NO_WARNINGS 1
#define _WINSOCK_DEPRECATED_NO_WARNINGS 1
//
#include <cstdio>
#include <vector>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <queue> 

using namespace std;

int main()
{
	const int m = 4;
	long long d[m] = { 1000000007, 1000000007,  15485383,        29};
	long long q[m] = { 1000010153, 1003010219, 982449707,  96209777};
	long long p[m] = {          1,          1,         1,         1};
	long long leftHash[m] = {   0,          0,         0,         0};
	long long righHash[m] = {   0,          0,         0,         0};

	int n;
	char c;
	scanf("%d", &n);
	scanf("%c", &c);

	int i = 0;

	while (scanf("%c", &c) > 0)
	{
		if (c == '\n')
			break;

		long long value = c - 'a';

		for (int i = 0; i < m; ++i)
		{
			leftHash[i] = (d[i] * leftHash[i] + value) % q[i];
			righHash[i] = (righHash[i] + p[i] * value) % q[i];
			p[i] = (p[i] * d[i]) % q[i];
		}		
	}

	bool result = true;

	for (int i = 0; i < m; ++i)
	{
		result &= leftHash[i] == righHash[i];
	}

	if (result)
	{
		printf("TAK");
	}
	else
	{
		printf("NIE");
	}
}