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

int l_hash_379, r_hash_379;
int l_hash_131, r_hash_131;
int l_hash_26, r_hash_26;
int C_379 = 263137;
int C_131 = 10000007;
int C_26 = 54018521;

bool is_palindrom() {
    return (l_hash_379 == r_hash_379) && (l_hash_131 == r_hash_131) && (l_hash_26 == r_hash_26);
}

int main() {
    int n;
    scanf("%d\n", &n);

    char c = 'a';
    int k_131 = 1, k_379 = 1, k_26 = 1;
    int t = 0;

    while (1) {
        if(scanf("%c", &c) == EOF) break;
        if(c == '\n') break;

        t = c - 'a';

        l_hash_379 = (((t*k_379)%C_379) + l_hash_379)%C_379;
        r_hash_379 = ((r_hash_379*379)%C_379 + t)%C_379;

        l_hash_131 = (((t*k_131)%C_131) + l_hash_131)%C_131;
        r_hash_131 = ((r_hash_131*131)%C_131 + t)%C_131;

        l_hash_26 = (((t*k_26)%C_26) + l_hash_26)%C_26;
        r_hash_26 = ((r_hash_26*26)%C_26 + t)%C_26;

        k_379 = (k_379*379)%C_379;
        k_131 = (k_131*131)%C_131;
        k_26 = (k_26*26)%C_26;        
    }
    
    printf(is_palindrom()?"TAK\n":"NIE\n");
    return 0;
}