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

using ll = long long;

constexpr ll powmod(ll a, ll n, ll p) {
  return n == 0 ? 1 : (n == 1 ? a : powmod(a * a % p, n/2, p) * powmod(a, n%2, p) % p);
}

constexpr int MAX = 20000000;
constexpr ll MOD = 1000000009;
constexpr ll P = 997;
constexpr ll PN = powmod(P, MAX, MOD);
constexpr ll PINV = powmod(P, MOD-2, MOD);
constexpr ll PINVN = powmod(PINV, MAX, MOD);
static_assert(P * PINV % MOD == 1, "asd");
static_assert(PN * PINVN % MOD == 1, "asd");


int next_char() {
  int c = getchar();
  if ('a' <= c && c <= 'z') {
    return c;
  }
  return EOF;
}

int main() {
  scanf("%*d\n");
  int c;
  int n = 0;
  ll h = 0, hrev = 0;
  ll p = 1, p_rev = PN;
  ll norm = PINVN * PINV % MOD;
  while ((c = next_char()) != EOF) {
    n++;
    h = (h + p * c) % MOD;
    hrev = (hrev + p_rev * c) % MOD;
    p = p * P % MOD;
    p_rev = p_rev * PINV % MOD;
    norm = norm * P % MOD;
  }
  hrev = hrev * norm % MOD;
  printf("%s\n", h == hrev ? "TAK" : "NIE");
}