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
//Potyczki 2018 - Palindrom - Korneliusz Litman

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define ll long long
#define ull unsigned long long
using namespace std;

const ull mod[] = {99999989, 1000000007, 100000037};
const ull cc = 31;
ull h1[3], h2[3];

int main()
{
    //ios_base::sync_with_stdio(0);
    //cin.tie(0);
    //cout << sizeof(t);

    char c;
    int n;
    //ull h1 = 0, h2 = 0;
    ull pot[] = {1, 1, 1};

    cin >> n;
    
    c = getchar();
    c = getchar();
    while (c >= 'a' && c <= 'z')
    {

        h1[0] = (h1[0]*cc + (ull)(c-'a' + 1))%mod[0];
        h2[0] = (h2[0] + (ull)(c-'a' + 1) * pot[0])%mod[0];
        pot[0] = (pot[0]*cc)%mod[0];
        
        
        h1[1] = (h1[1]*cc + (ull)(c-'a' + 1))%mod[1];
        h2[1] = (h2[1] + (ull)(c-'a' + 1) * pot[1])%mod[1];
        pot[1] = (pot[1]*cc)%mod[1];
        
        
        h1[2] = (h1[2]*cc + (ull)(c-'a' + 1))%mod[2];
        h2[2] = (h2[2] + (ull)(c-'a' + 1) * pot[2])%mod[2];
        pot[2] = (pot[2]*cc)%mod[2];
        
        c = getchar();
    }
    if (h1[0] == h2[0] && h1[1] == h2[1] && h1[2] == h2[2]) cout << "TAK";
    else cout << "NIE";
}