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>

long long hash1;
long long hash2;
long long ter1, ter2;
long long pod = 31;
long long odw;
int mod = 1000696969;

long long binpow(long long p, int wyk, int mod) {
    long long ret = 1;
    while (wyk != 0) {
        if (wyk % 2 == 1)
            ret = (ret * p) % mod;
        p = (p * p) % mod;
        wyk /= 2;
    }
    return ret;
}

int main() {
    int N;
    scanf("%d ", &N);
    N = 500000000;
    odw = binpow(pod, mod - 2, mod);
    ter1 = pod, ter2 = binpow(pod, N, mod);
    int c;
    while ((c = getchar_unlocked()) && c != '\n') {
        N--;
        c -= 'a';
        hash1 = (hash1 + ter1 * c) % mod;
        hash2 = (hash2 + ter2 * c) % mod;
        ter1 = (ter1 * pod) % mod;
        ter2 = (ter2 * odw) % mod;
    }
    hash1 *= binpow(pod, N, mod);
    hash1 %= mod;
    if (hash1 != hash2) {
        printf("NIE");
        return 0;
    }
    printf("TAK");
    return 0;
}