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
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>

using namespace std;

long long hashA[2];
long long hashB[2];
long long hashC[2];
long long lastS[3] = {1,1,1};
int size = 0;
int cnt = 0;

int S[3] = {727,577,431};
int P[3] = {722222227,573258349,700000001};
int MAX_SIZE = 20*1000*1000+1005;
const long long BIG_ONE = 1000*1000*1000*1000*1000;

int main(){
  cin >> size;
  size = 0;

  while(true){
    int i = getchar();
    if(i == EOF)
      break;
    //cout << i << endl;

    hashA[0] += (int)i*lastS[0];
    if(hashA[0] > BIG_ONE)
      hashA[0] %= P[0];
    hashA[1] *= S[0];
    hashA[1] += i;
    if(hashA[1] > BIG_ONE)
      hashA[1] %= P[0];

    hashB[0] += (int)i*lastS[1];
    if(hashB[0] > BIG_ONE)
      hashB[0] %= P[1];
    hashB[1] *= S[1];
    hashB[1] += i;
    if(hashB[1] > BIG_ONE)
      hashB[1] %= P[1];

    hashC[0] += (int)i*lastS[2];
    if(hashC[0] > BIG_ONE)
      hashC[0] %= P[2];
    hashC[1] *= S[2];
    hashC[1] += i;
    if(hashC[1] > BIG_ONE)
      hashC[1] %= P[2];

    lastS[0] *= S[0];
    lastS[1] *= S[1];
    lastS[2] *= S[2];

    lastS[0] %= P[0];
    lastS[1] %= P[1];
    lastS[2] %= P[2];

    size++;
    cnt++;
  }

  if(hashA[0] == hashA[1] && hashB[0] == hashB[1] && hashC[0] == hashC[1])
    cout << "TAK" << endl;
  else
    cout << "NIE" << endl;

}