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
#include <stdio.h>
#include <sys/stat.h>
#include <string.h>

int get_input_size() {
  struct stat st;
  fstat(0, &st);
  return st.st_size;
} 

typedef long long int int64_t;


int64_t _exp(int64_t a, int64_t n, int64_t mod) {
  if (n == 0LL)
    return 1LL % mod;
  if (n % 2LL == 1LL) {
    return (a * _exp(a, n - 1LL, mod)) % mod;
  }
  a = _exp(a, n / 2LL, mod);
  return (a * a) % mod;
}

inline int64_t _pow(int64_t a, int64_t n, int64_t mod) {
  int64_t result = 1LL % mod;
  for (;;) {
    if (n & 1LL)
      result = (result * a) % mod;
    n >>= 1LL;
    if (!n)
      break;
    a = (a * a) % mod;
  }
  return result;
}

#define exp _exp
#define pow _pow

int main() {
  int nn = get_input_size();
  char buf[64];
  memset(buf, 0, 64);
  scanf("%s", buf);
  int x = strlen(buf);
  int n = nn - x - 2;
  getchar_unlocked();
  
  int64_t lh[2] = {0, 0}, rh[2] = {0, 0};
  int64_t P[2] = {313, 331};
  int64_t Q[2] = {1e9 + 7, 1e9 + 7};

  for (int i = 0; i < n; ++i) {
    int64_t c = getchar_unlocked();
    for (int j = 0; j < 2; ++j) {
      /*
      if (j == 0) {
        printf("%d lh[j] = %lld * %lld + %lld\n", i, lh[j], P[j], c);
        printf("%d rh[j] = %lld + %lld * %lld\n", i, rh[j], c,
               exp(P[j], i, Q[j]));
      }
      */
      lh[j] = ((((lh[j] * P[j]) + c) % Q[j]) + Q[j]) % Q[j];
      rh[j] = (((rh[j] + c * pow(P[j], i, Q[j])) % Q[j]) + Q[j]) % Q[j];
    }
  }

  /*
  puts("");

  printf("%d\n", n);
  printf("%lld == %lld :: %lld = %lld\n", lh[0], rh[0], lh[1], rh[1]);
  */

  if (lh[0] == rh[0] && lh[1] == rh[1]) {
    puts("TAK");
  } else {
    puts("NIE");
  }

  return 0;
}