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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define ll long long

long long compute_hash(string const& s) {
    const int p = 31;
    const int m = 1e9 + 9;
    long long hash_value = 0;
    long long p_pow = 1;
    
    for (char c : s) {
        hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
        p_pow = (p_pow * p) % m;
    }
    
    return hash_value;
}

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

    int n;
    cin >> n;

    char c;
    ll l1 = 0, l2 = 0, r1 = 0, r2 = 0,p1 = 31, p2 = 33, m1 = 1e9 + 9, m2 = 1e9 + 6421, P1 = 1, P2 = 1, cc;
    while(cin >> c) {
        cc = c - 'a' + 1;
        
        l1 = (l1 + P1 * cc) % m1; P1 = (P1 * p1) % m1;
        l2 = (l2 + P2 * cc) % m2; P2 = (P2 * p2) % m2;
        r1 = (p1 * r1 + cc) % m1;
        r2 = (p2 * r2 + cc) % m2;
    }

    if(l1 == r1 && l2 == r2) cout << "TAK";
    else cout << "NIE";

    return 0;
}