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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>

inline void read(char *c) {
    while (*c<33) *c=getc_unlocked(stdin);
}

int main() {
    const long long P = 17171711, Q = 181358081;
    long long _P = 1;
    char c = 0;
    int left_hash = 0, right_hash = 0;
    int n, i = 0;
    
    scanf("%d", &n);
    read(&c);
    
    while (c >= 33) {
        left_hash = (left_hash + c * _P) % Q;
        right_hash = (right_hash * P + c) % Q;
        
        _P = (P * _P) % Q;
        c = getc_unlocked(stdin);
        i++;
        if (i == n) break;
    }
    
    puts(left_hash == right_hash ? "TAK" : "NIE");
}