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
#include <bits/stdc++.h>
#define ll long long
#define debug if(0)

const ll MOD = 1e9+21;
ll x[3] = {31, 59, 101};
ll pot[3] = {1, 1, 1};
ll H[3]; // hash
ll HR[3]; // hash reverse

int main(){
    int n; std::cin >> n;
    char c;
    while (std::cin >> c){
        for (int i = 0; i < 3; i++){
            H[i] = (H[i] + (ll)(c-'a'+1) * pot[i]) % MOD;
            HR[i] = (HR[i] * x[i] + (ll)(c-'a'+1)) % MOD;
            pot[i] = (pot[i] * x[i]) % MOD;
        }

        debug{
            for (int i = 0; i < 3; i++)
                std::cout << "H[" << i << "]: " << H[i] << ", HR[" << i << "]: " << HR[i] << "\n";
        }
    }

    (H[0] == HR[0] && H[1] == HR[1] && H[2] == HR[2]) ? std::cout << "TAK\n" : std::cout << "NIE\n";
}