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
#include <iostream>
#include <vector>
#include <cstdint>


using namespace std;

template <unsigned int M, unsigned  int base>
class hashh{
public:
    hashh(): val(0),rp(1) {};
    uint32_t val;
    uint32_t rp;
    void add(uint32_t a){
        val = (val + rp*a)%M;
        rp=(rp*base)%M;
    }
};

template <unsigned int M, unsigned  int base>
class rev_hash{
public:
    rev_hash(): val(0) {};
    uint32_t val;
    void add(uint32_t b0){
        val = (val*base + b0)%M;
    }
};


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    hashh<32711, 31> h1;
    rev_hash<32711, 31> rh1;
    hashh<32999, 29> h2;
    rev_hash<32999, 29> rh2;
    hashh<42709, 29> h3;
    rev_hash<42709, 29> rh3;

    char c;

    while (cin >> c && isalpha(c)) {
        uint32_t t = c - 'a';
        h1.add(t);
        rh1.add(t);
        h2.add(t);
        rh2.add(t);
        h3.add(t);
        rh3.add(t);
    }
    cout<< ((rh1.val==h1.val && rh2.val==h2.val && rh3.val==h3.val)?"TAK":"NIE")<<endl;
    return 0;
}