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
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>
#include <cstdio>
#include <string>
#include <sstream> 
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <cassert>
using namespace std;
using ll = long long;
const int INF = 1e9;

class Hasher {
public:
    Hasher(ll base_, ll mod_) : base(base_), mod(mod_) {}

    void add_char(char c) {
        int x = c-'a'+1;
        // update hash
        h = (h*base + x) % mod;

        // update reversed hash
        rev_h = (rev_h + roll_exp*x) % mod;

        roll_exp = (roll_exp * base) % mod;
    }

    bool is_palindrome() const {
        return h == rev_h;
    }
private:
    ll base;
    ll mod;
    ll h = 0;
    ll rev_h = 0;
    ll roll_exp = 1;
};

class MultipleHasher {
public:
    MultipleHasher(const vector<int>& bases, const vector<int>& modulos) {
        for (auto base : bases) {
            for (auto mod : modulos) {
                hashers.push_back(Hasher(base, mod));
            }
        }
    }

    void add_char(char c) {
        for (auto& hasher : hashers) {
            hasher.add_char(c);
        }
    }

    bool is_palindrome() const {
        for (const auto& hasher : hashers) {
            if (!hasher.is_palindrome()) {
                return false;
            }
        }
        return true;
    }

private:
    vector<Hasher> hashers;
};


int main() {
    ios_base::sync_with_stdio(0);
    int n;
    scanf("%d\n", &n);

    // many real constants
    /*
    const vector<int> BASES = {31, 37, 41, 43, 47};
    const vector<double> DOUBLE_MODULOS = {1e9+7, 1e9+9, 1e9+21, 1e9+33, 1e9+87, 1e9+93, 1e9+97, 1e9+103};
    const vector<int> MODULOS = {DOUBLE_MODULOS.begin(), DOUBLE_MODULOS.end()};
    */

    // production real constants
    const vector<int> BASES = {31};
    //const vector<double> DOUBLE_MODULOS = {1e9+7, 1e9+21, 1e9+87};
    const vector<double> DOUBLE_MODULOS = {1e9+21, 1e9+87};
    const vector<int> MODULOS = {DOUBLE_MODULOS.begin(), DOUBLE_MODULOS.end()};

    // constants for testing
    /*
    const vector<int> BASES = {31};
    const vector<int> MODULOS = {1000000000+7};
    */

    MultipleHasher hasher(BASES, MODULOS);
    char c;
    while (scanf("%c", &c) == 1) {
        if (!(c >= 'a' and c <= 'z')) {
            break;
        }
        hasher.add_char(c);
    }
    if (hasher.is_palindrome()) {
        printf("TAK\n");
    } else {
        printf("NIE\n");
    }
    return 0;
}