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
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <algorithm>

#define DB if(0)

#define MAX 20000009
#define N 1000

long long MOD = 1000289;

long long forwardTable[MAX/N+1], backward[MAX/N+1];

char permuteChars[] = {21,10,2,6,5,24,14,0,19,1,4,26,16,22,3,8,15,11,20,9,18,25,13,12,7,23,17};
int cache[N+1];

using namespace std;

long long power(long long v, long long by, int to) {
  if (to <= 0) return v;
  if (to % 2) return power(v * by, by, to-1);
  return power(v, by * by, to/2);
}

void count(int step, int length) {
  long long mod = MOD;
  for (int i=length-1; i>=0; i--) {
    backward[step] = backward[step] + (cache[i] + 1) * mod;
    forwardTable[step] = forwardTable[step] + (cache[length-i-1] + 1) * mod;
    mod *= MOD;
  }
}

long long computeHash(long long *tab, int firstLen, int tabLen) {
  int currentPartLen = firstLen;
  long long mod = 1, hash = tab[0];
  for (int i=1; i<=tabLen; i++) {
    mod *= power(MOD, MOD, currentPartLen-1);

    hash = hash + tab[i] * mod;
    
    currentPartLen = N;
  }

  return hash;
}

int main() {
  int n, position = 0, step = 0;
  char c;
  bool first = true;
  cin >> n;

  while (cin.get(c)) {
    position %= N;
    if (position == 0 && !first) {
      count(step, N);
      step++;
    }
    if (c < 'a' || c > 'z') continue;
    first = false;
    c -= 'a';
    c = permuteChars[c];
    cache[position] = c;
    position++;
  }

  int lastPartLen = position;
  if (lastPartLen) count(step, lastPartLen);
  else {
    step--;
    lastPartLen = N;
  }
  for (int i=0; i<=step/2; i++) {
    swap(backward[i], backward[step-i]);
  }

  long long forwardTotal = computeHash(forwardTable, N, step), backwardTotal = computeHash(backward, lastPartLen, step);

  if (forwardTotal == backwardTotal) cout << "TAK\n";
  else  cout << "NIE\n";
}