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

#define lint unsigned long long

lint pow(lint base, lint exp) {
    if(exp == 0) return 1;
    if(exp % 2 == 1)
         return base * pow(base, exp - 1);
    lint tmp = pow(base, exp / 2);
    return tmp * tmp;
}

int main() {
    const lint p = 2000000011, p_inv = 4973211295069853603ULL, max_len = 20000000 + 20;
    char c;
    lint len = 0, a = 0, b = 0, a_p = p, b_p = pow(p, max_len), a_p_e = 0, b_p_e = max_len + 1, n;
    std::scanf("%lld\n", &n);
    while(std::scanf("%c", &c) == 1) {
        if(!(c <= 'z' && c >= 'a')) continue;
        a_p_e += 1;
        b_p_e -= 1;
        a = (a + c * a_p);
        b = (b + c * b_p);
        a_p = (a_p * p);
        b_p = (b_p * p_inv);
    }

    if(a * pow(p, b_p_e - 1) == b)
        std::printf("TAK\n");
    else
        std::printf("NIE\n");

    return 0;
}