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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <iostream>
#include <fstream>
#include <vector>

using ull = unsigned long long;
using type = unsigned;

template<type M>
inline void multiply(type& lhs, type rhs) {
    lhs = ((ull)lhs * (ull)rhs) % M;
}

template<type M>
type qpow(type x, type n) {
    type result = 1UL;
    type pow = x % M;

    while (n > 0) {
        if ((n & 1) == 1) {
            multiply<M>(result, pow);
        }

        multiply<M>(pow, pow);
        n /= 2;
    }

    return result;
}

template<type M>
inline type modinv(type x) {
    return qpow<M>(x, M - 2);
}

template<type M>
inline void add(type& lhs, type rhs) {
    lhs = (lhs + rhs) % M;
}

template<type M>
inline void divide(type& lhs, type rhs) {
    multiply<M>(lhs, modinv<M>(rhs));
}

template<type B, type M>
class ForwardHash {
public:
    inline type getHash() const {
        return hash;
    }

    void addChar(char c) {
        type charHash = (unsigned)c - (unsigned)('a') + 1;
        multiply<M>(charHash, basePow);

        add<M>(hash, charHash);
        multiply<M>(basePow, B);
    }

private:
    type hash{0UL};
    type basePow {B};
};

template<type B, type M, size_t L>
class ReverseHash {
public:
    inline type getHash() const {
        return hash;
    }

    void addChar(char c) {
        type charHash = (unsigned)c - (unsigned)('a') + 1;
        multiply<M>(charHash, basePow);

        add<M>(hash, charHash);
        multiply<M>(basePow, baseInv);
        --idx;
    }

    void removeOffset() {
        divide<M>(hash, qpow<M>(B, idx));
        idx = 0;
    }

private:
    type hash{0UL};
    size_t idx{L};
    type basePow {qpow<M>(B, L)};
    type baseInv {modinv<M>(B)};
};

template<type B, type M, size_t L>
inline bool operator ==(const ForwardHash<B, M>& forwardHash, const ReverseHash<B, M, L>& reverseHash) {
    return forwardHash.getHash() == reverseHash.getHash();
}

const size_t MAX_N = static_cast<size_t>(2e7);
const type BASE = 29;

const type MOD1 = static_cast<type>(1e9 + 9);
const type MOD2 = static_cast<type>(1e9 + 696969);
const type MOD3 = static_cast<type>(982450921);

int main() {
    std::string line;
    std::getline(std::cin, line);

    auto hash = ForwardHash<BASE, MOD1>();
    auto revHash = ReverseHash<BASE, MOD1, MAX_N>();

    auto hash2 = ForwardHash<BASE, MOD2>();
    auto revHash2 = ReverseHash<BASE, MOD2, MAX_N>();

    auto hash3 = ForwardHash<BASE, MOD3>();
    auto revHash3 = ReverseHash<BASE, MOD3, MAX_N>();

    char c;

    while(std::cin.get(c) && c >= 'a' && c <= 'z') {
        hash.addChar(c);
        revHash.addChar(c);

        hash2.addChar(c);
        revHash2.addChar(c);

        hash3.addChar(c);
        revHash3.addChar(c);
    }

    revHash.removeOffset();
    revHash2.removeOffset();
    revHash3.removeOffset();

    bool palindrome = (hash == revHash) && (hash2 == revHash2) && (hash3 == revHash3);

    std::cout << (palindrome ? "TAK" : "NIE") << std::endl;

    return 0;
}