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
#include <cstdio>
using namespace::std;

const int MOD1 = 1000000087, MOD2 = 1000001699;

long long h1, h2, H1, H2, p = 29;

void liczba(int &x) {
    x = 0;
    char c;
    bool bylo = false;
    while ((c = getchar_unlocked())) {
        if (c != EOF and c != '\n' and c != ' ' and c != '\r') {
            x *= 10;
            x += c - '0';
            bylo = true;
        } else if (bylo) break;
    }
}

int n;

int main() {
    liczba(n);
    char c;
    bool bylo = false;
    long long pot1 = p, pot2 = p;
    while ((c = getchar_unlocked())) {
        if (c != EOF and c != '\n' and c != ' ' and c != '\r') {
            h1 = p * (h1 + (c - 'a'));
            if (h1 > MOD1) h1 %= MOD1;
            h2 = (h2 + pot1 * (c - 'a'));
            if (h2 > MOD1) h2 %= MOD1;
            pot1 = p * pot1;
            if (pot1 > MOD1) pot1 %= MOD1;
            H1 = (p * (H1 + (c - 'a'))) % MOD2;
            H2 = (H2 + pot2 * (c - 'a')) % MOD2;
            pot2 = p * pot2;
            if (pot2 > MOD2) pot2 %= MOD2;
            bylo = true;
        } else if (bylo) break;
    }
    if (h1 == h2 and H1 == H2) printf("TAK");
    else printf("NIE");
}