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

using namespace std;

long long H1[3];
long long H2[3];

long long P=29921;
long long Q[3]={858602117, 858602177, 694850419};

long long pot[3];

int main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);

   int n;
   cin>>n;

   for(int i=0;i<3;i++){
    pot[i]=1;
   }
   char a;
   while(cin>>a){
    for(int i=0;i<3;i++){
        H1[i]=(H1[i]*P+(long long)a)%Q[i];

        H2[i]=(H2[i]+(long long)a*pot[i])%Q[i];
        pot[i]=(pot[i]*P)%Q[i];
    }
   }

   int sp=0;
   for(int i=0;i<3;i++){
    if(H1[i]!=H2[i])sp=1;
   }
   if(sp==1)cout<<"NIE";
   else cout<<"TAK";

}