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
#include <cstdio>
#include <utility>

using LL = long long;

template<LL BASE, LL MOD>
struct Hash
{
  LL hash1 = 0, hash2 = 0, x = 1;

  void operator()(char c)
  {
    hash1 = (hash1 * BASE % MOD + c) % MOD;
    hash2 = (hash2 + c * x % MOD) % MOD;
    x = (x * BASE) % MOD;
  }

  std::pair<LL, LL> get() const { return { (hash1 + MOD) % MOD, (hash2 + MOD) % MOD }; }
  bool test() const { auto res = get(); return res.first == res.second; }
};

using Hash3659 = Hash<31, 2147483659>;
using Hash2801 = Hash<31, 2147482801>;

int main()
{
  int n; std::scanf("%i ", &n);
  Hash3659 hash1{}; Hash2801 hash2{};

  char c;
  while ('\n' != (c = getchar_unlocked())) {
    hash1(c); hash2(c);
  }

  std::printf("%s\n", (hash1.test() && hash2.test()) ? "TAK" : "NIE");
}