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

template <typename T> T load() { T r; cin >> r; return r; }
template <typename T> vector<T> loadMany(int n) { vector<T> rs(n); generate(rs.begin(), rs.end(), &load<T>); return rs; }

template <int m> struct Mint {
    Mint():val(0){}
    Mint(int raw):val(raw % m){}
    Mint(long long raw):val(raw % m){}
    friend Mint operator+(Mint a, Mint b) { return a.val + b.val; }
    friend Mint operator*(Mint a, Mint b) { return (long long)a.val * b.val; }
    friend bool operator==(Mint a, Mint b) { return a.val == b.val; }
    int val;
};

template <int p, int m> struct Palhash {
    Palhash():normal(0),reverse(0),pi(1){}
    void append(int x) {
        normal = normal + pi * x;
        reverse = p * reverse + x;
        pi = pi * p;
    }
    bool isPalindrome() const {
        return normal == reverse;
    }
    Mint<m> normal, reverse, pi;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    load<int>();
    auto c = char();
    auto h1 = Palhash<907, 1000000349>();
    auto h2 = Palhash<821, 1000000363>();
    while (cin >> c)
        h1.append(c - 'a'), h2.append(c - 'a');
    auto answer = h1.isPalindrome() and h2.isPalindrome();
    cout << (answer ? "TAK" : "NIE") << '\n';
}