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

int main() {
    const long long P = 31;
    const long long M = 1e9 + 7;
    const long long P2 = 37;
    const long long M2 = 2e9 + 11;
    
    long long leftHash = 0;
    long long rightHash = 0;
    long long pToI = 1;

    long long leftHash2 = 0;
    long long rightHash2 = 0;
    long long pToI2 = 1;

    int n;
    cin >> n;
    char x;
    x = getchar();
    while ((x = getchar()) != EOF) {
        if (x < 'a' || x > 'z') {
            break;
        }
        leftHash = (leftHash + (x - 'a') * pToI) % M;
        rightHash = (rightHash * P + (x - 'a')) % M; 
        pToI = (pToI * P) % M;

        leftHash2 = (leftHash2 + (x - 'a') * pToI2) % M2;
        rightHash2 = (rightHash2 * P2 + (x - 'a')) % M2; 
        pToI2 = (pToI2 * P2) % M2;
    }
    cout << ((leftHash == rightHash && leftHash2 == rightHash2) ? "TAK" : "NIE");
    return 0;
}