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

using namespace std;
using ll = long long;

constexpr int N_PRIMES = 4;
const ll PRIMES[] = {
    40763, 55733, 37021, 35117
};
constexpr ll M = 1000000009;

int main() {
    int N;
    scanf("%d", &N);
    
    
    vector<ll> fw(N_PRIMES), bw(N_PRIMES);
    vector<ll> W(N_PRIMES, 1);
    
    while (true) {
        char ch = getchar();
        while (ch == 10) ch = getchar();
        if (ch == EOF) break;
        //cerr << "`" << (int)ch << "`" << endl;
        
        for (int j = 0; j < N_PRIMES; ++j){ 
            
            fw[j] *= PRIMES[j];
            fw[j] += ch;
            fw[j] %= M;
            
            bw[j] += ch * W[j];
            bw[j] %= M;
            
            W[j] *= PRIMES[j];
            W[j] %= M;
        }
    }
    
    bool pal = true;
    for (int j = 0; j < N_PRIMES; j++) {
        cerr << fw[j] << "," << bw[j] << endl;
        if (fw[j] != bw[j])
            pal = false;
    }
    
    cout << (pal ? "TAK" : "NIE") << endl;
}