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
57
58
59
#include<iostream>
#include<list>
#include<stdio.h>
#include<map>
#include<set>
#include<vector>
using namespace std;
#define ull unsigned long long int
#define FOR(i,n) for(int i=0;i<(n);++i)
#define FORI(i,start,n) for(int i=(start);i<(n);++i)
#define FORit(it,collection) for(auto it = collection.cbegin(); it != collection.cend(); it++)
#define SKIP -5000
#define znakow 26
#define DEBUG 0
#define dcout DEBUG && cout
int inline min(int a,int b){return a>b?b:a;}
int inline max(int a,int b){return a<b?b:a;}
int main(){
    int n;
    scanf("%d", &n);
    //cin>>n;
    char c;
    ull leftHash0=0, rightHash0=0;
    ull leftHash1=0, rightHash1=0;
    ull leftHash2=0, rightHash2=0;
    ull leftHash3=0, rightHash3=0;
    ull ck0=1;
    ull ck1=1;
    ull ck2=1;
    ull ck3=1;
    do {scanf("%c", &c);} while((c<'a') || ('z'<c));
    do {//printf(":%c:\n", c);
        ull cc=c-'a'+1;

        rightHash0=(rightHash0*29+cc)%((1<<30)-1);
        leftHash0=(leftHash0+ck0*cc)%((1<<30)-1);
        ck0=(ck0*29)%((1<<30)-1);

        rightHash1=(rightHash1*31+cc)%999999937;
        leftHash1=(leftHash1+ck1*cc)%999999937;
        ck1=(ck1*31)%999999937; 

        rightHash2=(rightHash2*421+cc)%999999677;
        leftHash2=(leftHash2+ck2*cc)%999999677;
        ck2=(ck2*421)%999999677;

        rightHash3=(rightHash3*37+cc)%1000000007;
        leftHash3=(leftHash3+ck3*cc)%1000000007;
        ck3=(ck3*37)%1000000007;

        if(scanf("%c", &c)!=1)break;
    } while(('a'<=c) & (c<='z'));
    if(leftHash0!=rightHash0 || leftHash1!=rightHash1 || leftHash2!=rightHash2 || leftHash3!=rightHash3){
        printf("NIE\n");
        return 0;
    }
    printf("TAK\n");
    return 0;
}