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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;

typedef long long ll;

ll P[] = {809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997};
int H[20000];

int MOD = 2000000413;

ll pw(int bits, int p) {
    ll res = 1L;
    for (int i=0;i<11;i++) {
        if (bits && ((1<<i))) {
            res *= p;
            res %= MOD;
        }
    }
    return res;
}

ll do_hash(ll val, int i, int p) {
    int bits = P[(i%26) + 1] ^ p;
    ll tt = pw(bits, p);
    val += tt;
    val %= MOD;
    return val;
}


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

    if (n==0) {
        cout << "NIE" << endl;
        return 0;
    }

    ll h1 = 1L;
    for (int i=0;i<n/2;i++) {
        cin >> c;
        int p = P[int(c-'a')];
        h1 = do_hash(h1, i, p);
    }

    if (n&1) cin >> c;

    ll h2 = 1L;
    for (int i=n/2-1;i>=0;i--) {
        cin >> c;
        int p = P[int(c-'a')];
        h2 = do_hash(h2, i, p);
    }

    if (h1 == h2) {
        cout << "TAK" << endl;
    } else {
        cout << "NIE" << endl;
    }

    return 0;
}