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

using namespace std;

typedef long long ll;

#ifdef DEBUG
#define DEB(x) (cerr << x)
#else
#define DEB(x)
#endif

const int COUNT = 1;

const int PRIMES[COUNT][2] = {
        {1085957, 1261238057},
//        {1262753, 1641382529},
//        {1737403, 1670626619},
//        {1539347, 1459240927},
//        {1762637, 1371784943},
//        {1223419, 1275371351},
//        {1782611, 1011698693},
//        {1666177, 1457191663},
//        {1328563, 1294606861},
//        {1609627, 1625209283},
//        {1417183, 1465994851},
};

int hash1[COUNT] = {};
int hash2[COUNT] = {};
int base[COUNT] = {};


int main() {

//    for (int i = 0; i < COUNT; ++i) {
//        cout << "i=" << i << " " << PRIMES[i][0] << ", " << PRIMES[i][1] << "\n";
//    }

    for (int h = 0; h < COUNT; ++h) {
        base[h] = 1;
    }

    int _n;
    cin >> _n;
    char c;
    bool ok = true;
    for (int i = 0; cin >> c; ++i) {
//        cout << "(" << c << ")\n";
        ok = true;

        for (int h = 0; h < COUNT; ++h) {
            ll mul = PRIMES[h][0];
            ll mod = PRIMES[h][1];
            hash1[h] = (hash1[h] + (1LL * base[h] * c) % mod) % mod;
            hash2[h] = (1LL * hash2[h] * mul + c) % mod;
            base[h] = (1LL * base[h] * mul) % mod;
//            DEB("h=" << h << " " << (hash1[h] == hash2[h] ? "OK" : "--") << " hash1=" << hash1[h] << " hash2="
//                     << hash2[h] << "\n");
            if (hash1[h] != hash2[h]) {
                ok = false;
            }
        }

    }
    cout << (ok ? "TAK\n" : "NIE\n");
}