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
#include <iostream>
using namespace std;
typedef long long ll;

const ll mod1 = 1e9+7, mod2 = 1e9+696969;
const ll base1 = 997, base2 = 257;

int32_t main(){
    int n;
    cin >> n;
    n = 0;
    ll hash1 = 0, hash2 = 0;
    ll revHash1 = 0, revHash2 = 0;

    ll cpBase1 = 1, cpBase2 =1;
    getc(stdin);
    for(;;){
        char c = getc(stdin);
        if(c < 'a' || c > 'z')
            break;
        hash1 = (hash1 * base1 + c) % mod1;
        hash2 = (hash2 * base2 + c) % mod2;

        revHash1 = (revHash1 + (c* cpBase1))% mod1;
        revHash2 = (revHash2 + (c* cpBase2))% mod2;
        
        cpBase1 = (cpBase1 * base1) % mod1;
        cpBase2 = (cpBase2 * base2) % mod2;
    }

    //cout<<hash1<<" "<<revHash1<<endl;
    //cout<<hash2<<" "<<revHash2<<endl;
    
    if(hash1 == revHash1 && hash2 == revHash2)
        cout<<"TAK\n";
    else
        cout<<"NIE\n";
}