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

const long long p = 29;
const int PRIMES = 3;
const long long modp[PRIMES] = {1000000123L, 1000123567L, 1122345677L};

int main()
{
    long long right[PRIMES], left[PRIMES], leftp[PRIMES];
    for (int i = 0; i < PRIMES; ++i) {
        right[i] = left[i] = 0;
        leftp[i] = 1;
    }
    int n;
    scanf("%d", &n);
    char c;
    while (scanf("%c", &c) != EOF) {
        if (c < 'a')
            continue;
//       printf("c='%c'\n", c);
        c -= 'a';
        for (int i = 0; i < PRIMES; ++i) {
            right[i] = (c + p * right[i]) % modp[i];
            left[i]  = (left[i] + leftp[i] * c) % modp[i];
            leftp[i] = p * leftp[i] % modp[i];
        }
    }
    for (int i = 0; i < PRIMES; ++i)
        if (left[i] != right[i]) {
            printf("NIE\n");
            return 0;
        }
    printf("TAK\n");
    return 0;
}