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
#include <iostream>
using namespace std;
int main() {
    ios_base::sync_with_stdio(0);
    long long int mod1 = 1000000009;
    long long int mod2 = 1000000007;
    long long int mod3 = 1000000861;
    //long long int mod4 = 1000004329;
    long long int pow1 = 1;
    long long int pow2 = 1;
    long long int pow3 = 1;
    //long long int pow4 = 1;
    char z;
    long long int hash1 = 0;
    long long int hash2 = 0;
    long long int hash3 = 0;
    long long int hash4 = 0;
    long long int hash5 = 0;
    long long int hash6 = 0;
    //long long int hash7 = 0;
    //long long int hash8 = 0;

    int n;
    cin>>n;
    while(cin>>z){
        hash1 += (((int)z - 96) * pow1)%mod1;
        hash1 %= mod1;
        hash3 += (((int)z - 96) * pow2)%mod2;
        hash3 %= mod2;
        hash5 += (((int)z - 96) * pow3)%mod3;
        hash5 %= mod3;
        //hash7 += (((int)z - 96) * pow4)%mod4;
        //hash7 %= mod4;

        hash2 = (((hash2 * 31)%mod1)+((int)z - 96))%mod1;
        hash4 = (((hash4 * 31)%mod2)+((int)z - 96))%mod2;
        hash6 = (((hash6 * 31)%mod3)+((int)z - 96))%mod3;
       // hash8 = (((hash8 * 31)%mod4)+((int)z - 96))%mod4;

        pow1*=31LL;
        pow1%=mod1;
        pow2*=31LL;
        pow2%=mod2;
        pow3*=31LL;
        pow3%=mod3;
       // pow4*=31LL;
       // pow4%=mod4;
    }
    if((hash1 == hash2) && (hash3 == hash4) && (hash5 == hash6)){
        cout<<"TAK";
    }
    else{
        cout<<"NIE";
    }
    return 0;
}