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
#include <iostream>
#define f first
#define s second
#define LL long long
#define ALL(V) V.begin(),V.end()
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define endl "\n"
#define debug(x) cerr<<#x<<": "<<x<<endl
using namespace std;
const LL N=1e6+69, base=30, mod1=1e9+7, mod2=1e9+9, mod3=1e9+696969;
int n;
char x;
int32_t main(void) {
    boost;
    long long p1=1, h1l=0, h1p=0;
    long long p2=1, h2l=0, h2p=0;
    long long p3=1, h3l=0, h3p=0;
    cin>>n;
    while(cin>>x) {
        int a=x-'a'+1;
        h1l*=base;
        h1l+=a;
        h1l%=mod1;
        h1p+=(p1*a)%mod1;
        h1p%=mod1;
        p1*=base;
        p1%=mod1;
        
        h2l*=base;
        h2l+=a;
        h2l%=mod2;
        h2p+=(p2*a)%mod2;
        h2p%=mod2;
        p2*=base;
        p2%=mod2;
        
        h3l*=base;
        h3l+=a;
        h3l%=mod3;
        h3p+=(p3*a)%mod3;
        h3p%=mod3;
        p3*=base;
        p3%=mod3;
    }
    if(h1l==h1p && h2l==h2p && h3l==h3p) cout<<"TAK\n";
    else cout<<"NIE\n";
}