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
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <vector>

using namespace std;

int n;
string s;
char a;
vector <int> p,p2;      //p[300017],p2[400017];
const int M=1e9+7, m=10000019,m2=10000121,mp=300007,mp2=200003;
long long h,h1,h2,h3;

void P()
{
    p.resize(300017);
    p2.resize(200017);
    p[0]=29;
    p2[0]=31;
    for (int i=1; i<300007; i++)
    {
        p[i]=(p[i-1]*29)%m;
    }
    for (int i=1; i<200003; i++)
    {
        p2[i]=(p2[i-1]*31)%m2;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    if (n==0)
    {
        cin>>s;
        for (int i=0; i<s.size()/2; i++)
        {
            if (s[i]!=s[s.size()-1-i])
            {
                cout<<"NIE";
                return 0;
            }
        }
        cout<<"TAK";
    }
    else
    {
        P();
        for (int i=0; i<n/2; i++)
        {
            cin>>a;
            h+=((p[i%mp]*(a-96))%M);
            h1+=((p2[i%mp2]*(a-95))%M);
        }
        int ind=n/2-1, ind2=n/2-1;
        ind%=mp;
        ind2%=mp2;
        if (n%2==1)
        {
            cin>>a;
            //ind++;
        }
        for (int i=(n+1)/2; i<n; i++)
        {
            cin>>a;
            h2+=((p[ind]*(a-96))%M);
            h3+=((p2[ind2]*(a-95))%M);
            --ind;
            --ind2;
            if (ind==-1)
                ind+=mp;
            if (ind2==-1)
                ind2+=mp2;
        }
        if ((h==h2)&&(h1==h3))
            cout<<"TAK";
        else
            cout<<"NIE";
    }
    return 0;
}