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
#include <iostream>
#include <limits>

int length;
char znak;
long long hash0_left, hash0_right;

constexpr long long primes[] {800000011, 800000063 , 800000317};

template<int N, long long P = 0>
long long modpow(long long exp)
{
  long long n{N % P};
  long long result{1};
  while (exp > 0)
  {
    if (exp % 2 == 1)
      result = (result * n) % P;
    n = (n * n) % P;
    exp = exp / 2;
  }
  return result;
}

template<long long p>
struct hasher
{
  void hash(char znak)
  {
    length++;
    hash_left = (hash_left * 26 + (znak - 'a')) % p;
    hash_right = ((znak - 'a') * modpow<26, p>(length - 1) + hash_right) % p;
  }

  bool is_symmetrical()
  {
    return hash_left == hash_right;
  }

  long long hash_left{};
  long long hash_right{};
  int length{};
};

int main()
{
  std::cin >> length;
  length = 0;

  hasher<primes[0]> h1;
  hasher<primes[1]> h2;
  hasher<primes[2]> h3;
  while (std::cin >> znak)
  {
    h1.hash(znak);
    h2.hash(znak);
    h3.hash(znak);
  }
  if (h1.is_symmetrical() && h2.is_symmetrical() && h3.is_symmetrical())
    std::cout << "TAK\n";
  else
    std::cout << "NIE\n";
}