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
#include <bits/stdc++.h>
using namespace std;

const long long prime=37;
const long long prime2=41;
const long long mod=999999733;
const long long mod2=999999491;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int x,i;
    long long val,hsh_pref=0,hsh_suf=0,hsh_pref2=0,hsh_suf2=0,pot=1,pot2=1;
    char in;
    cin>>x;
    while(cin>>in)
    {
        val=(long long)(in-'a')+1;
        pot=(pot*prime)%mod;
        pot2=(pot2*prime2)%mod2;
        hsh_pref=(hsh_pref+val*pot)%mod;
        hsh_pref2=(hsh_pref2+val*pot2)%mod2;
        hsh_suf=((hsh_suf+val)*prime)%mod;
        hsh_suf2=((hsh_suf2+val)*prime2)%mod2;
    }
    if(hsh_pref==hsh_suf&&hsh_pref2==hsh_suf2)
        cout<<"TAK\n";
    else
        cout<<"NIE\n";
}