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
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;

const int N = 2;
int mod[N], seed[N], inv_seed[N];

int power(int a, int n, int mod) {
  int r = 1;
  while (n > 0) {
    if (n % 2) {
      r = (1LL * r * a) % mod;
    }
    a = (1LL * a * a) % mod;
    n /= 2;
  }
  return r;
}

bool isPrime(int n) {
  if (n == 1)
    return false;
  for (int i = 2; i * i <= n; ++i)
    if (n % i == 0)
      return false;
  return true;
}

void prepare() {
  const int BOUND_MOD = 500 * 1000 * 1000;
  const int BOUND_SEED = 100;
  
  for (int i = 0; i < N; ++i) {
    mod[i] = BOUND_MOD + rand() % BOUND_MOD;
    seed[i] = BOUND_SEED + rand() % BOUND_SEED;
    while (!isPrime(mod[i]))
      ++mod[i];
    inv_seed[i] = power(seed[i], mod[i] - 2, mod[i]);
  }
}

void solve() {
  const int BOUND_LEN = 20 * 1000 * 1000 + 5;
  
  int hash[N], rev_hash[N], pw[N], rev_pw[N];
  fill(hash, hash + N, 0);
  fill(rev_hash, rev_hash + N, 0);
  fill(pw, pw + N, 1);
  for (int i = 0; i < N; ++i) {
    rev_pw[i] = power(seed[i], BOUND_LEN, mod[i]);
  }
  
  int n;
  if (scanf("%d\n", &n)) {
    char c;
    int len = 0;
    while (true) {
      c = getchar();
      if (c == '\n' || c == EOF) break;
      for (int i = 0; i < N; ++i) {
        hash[i] = (hash[i] + 1LL * pw[i] * c) % mod[i];
        rev_hash[i] = (rev_hash[i] + 1LL * rev_pw[i] * c) % mod[i];
        pw[i] = (1LL * pw[i] * seed[i]) % mod[i];
        rev_pw[i] = (1LL * rev_pw[i] * inv_seed[i]) % mod[i];
      }
      ++len;
    }
    bool failed = false;
    for (int i = 0; i < N; ++i) {
      rev_hash[i] = (1LL * rev_hash[i] * power(inv_seed[i], BOUND_LEN - len + 1, mod[i])) % mod[i];
      if (hash[i] != rev_hash[i]) {
        failed = true;
        break;
      }
    }
    if (!failed) {
      cout << "TAK\n";
    } else {
      cout << "NIE\n";
    }
  }
}

int main() {
  srand(44747);
  prepare();
  solve();
}