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


int fastpow(int x, int p, int mod) {
    if (p == 0) return 1;
    int y = fastpow(x, p/2, mod);
    y = y * y % mod;
    if (p % 2 == 1) y = y * x % mod;
    return y;
}

struct Tester {
    int x, y, mod;
    int hx, hy;
    int n = 0;
    Tester(int x, int y, int mod):x(x), y(y), mod(mod) {
        assert((x * y % mod) == 1);
        hx = 0;
        hy = 0;
    }

    inline void put(int c) {
        hx = (hx * x + c) % mod;
        hy = (hy * y + c) % mod;
        n++;
    }

    void process() {
        hy = hy * fastpow(x, n - 1, mod) % mod;;
    }

    bool isok() {
        cerr << hx << " " << hy << "\n";
        return hx == hy;
    }
};
signed main() {
	ios_base::sync_with_stdio(0);
    srand(time(NULL));
    int n;
    cin >> n;

    char c;

    vector<int> mapping(10000);

    for (int i = 0; i < 10000; ++i) {
        mapping[i] = 100 + 6*i + rand()%3;
    }

    random_shuffle(begin(mapping), end(mapping));

    vector<Tester> v;
    v.push_back(Tester(999999, 387512391, 1e9 + 9));
    v.push_back(Tester(9971, 834620405, 1e9 + 7));
    v.push_back(Tester(7320394, 103838873, 111191111));

    while (cin >> c) {
        for (auto &x: v) x.put(mapping[c]);
    }

    for (auto &x: v) x.process();

    bool ok = true;
    for (auto &x: v) ok = ok && x.isok();

    if (ok) cout << "TAK\n";
    else cout << "NIE\n";

	return 0;
}