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
#include <stdint.h>
#include <stdio.h>


uint64_t doweliveindamnegypt(uint64_t a, uint64_t b, uint64_t m) {
  uint64_t p = a, r = 0;
  for(; b; b>>=1) {
    r = (r + (b & 1) * p) % m;
    p = (p + p) % m;
  }
  return r;
}


int main() {
  int ch;
  uint64_t const m = 0x77E55AE55AE55A6F;
  uint64_t const q = 0x5E4B57A18458AD1A;
  uint64_t l = 0, r = 0, x = 1;
  
  while((ch = getchar_unlocked()) != EOF) {
    if(ch < 'a') continue;
    l = (doweliveindamnegypt(l, q, m) + ch) % m;
    r = (r + doweliveindamnegypt(x, ch, m)) % m;
    x = doweliveindamnegypt(x, q, m);
  }
  
  fwrite(l == r ? "TAK\n" : "NIE\n", 1, 4, stdout);
  
  return 0;
}