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

const long long mod1 = 3000000019, mod2 = 20000000113, mod3 = 999999999961;
const long long baza1 = 26, baza2 = 29;

char c;
long long n, m1b1p, m1b1k, m1b2p, m1b2k, m2b1p, m2b1k, m2b2p, m2b2k, m3b1p, m3b1k, m3b2p, m3b2k, b11 = 1, b21 = 1, b12 = 1, b22 = 1, b13 = 1, b23 = 1;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    while (cin >> c)
    {
        m1b1p = (m1b1p * baza1 + c - 'a') % mod1;
        m1b1k = (m1b1k + (c - 'a') * b11) % mod1;
        m1b2p = (m1b2p * baza2 + c - 'a') % mod1;
        m1b2k = (m1b2k + (c - 'a') * b21) % mod1;
        m2b1p = (m2b1p * baza1 + c - 'a') % mod2;
        m2b1k = (m2b1k + (c - 'a') * b12) % mod2;
        m2b2p = (m2b2p * baza2 + c - 'a') % mod2;
        m2b2k = (m2b2k + (c - 'a') * b22) % mod2;
        m3b1p = (m3b1p * baza1 + c - 'a') % mod3;
        m3b1k = (m3b1k + (c - 'a') * b13) % mod3;
        m3b2p = (m3b2p * baza2 + c - 'a') % mod3;
        m3b2k = (m3b2k + (c - 'a') * b23) % mod3;

        b11 = (b11 * baza1) % mod1;
        b21 = (b21 * baza2) % mod1;
        b12 = (b12 * baza1) % mod2;
        b22 = (b22 * baza2) % mod2;
        b13 = (b13 * baza1) % mod3;
        b23 = (b23 * baza2) % mod3;
    }

    if (m1b1p == m1b1k && m1b2p == m1b2k && m2b1p == m2b1k && m2b2p == m2b2k && m3b1p == m3b1k && m3b2p == m3b2k)
        cout << "TAK\n";
    else
        cout << "NIE\n";
}