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
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
#include <cassert>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <limits>
#include <vector>
using namespace std;

using ll = long long;

constexpr int BLOCK_SIZE = 800;
constexpr int MAX_N = 20000000;
constexpr int MAX_HSH = (MAX_N + BLOCK_SIZE - 1) / BLOCK_SIZE;
constexpr int P1 = 1000000007;
constexpr int Q1 = 31;
constexpr int P2 = 999998309;
constexpr int Q2 = 29;

char buffer[BLOCK_SIZE+1], first_buf[BLOCK_SIZE+1];
pair<ll,ll> hsh1[MAX_HSH], hsh2[MAX_HSH];

#define SIZE(c) static_cast<int>((c).size())

template <int P, int Q>
pair<ll,ll> hash(int n) {
  ll l=0,r=0;
  for(int i=0;i<n;++i) {
    r = (r*Q + buffer[i] - 'a') % P;
    l = (l*Q + buffer[n-1-i] - 'a') % P;
  }
  return {l,r};
}

int read_buf() {
  cin.get(buffer, BLOCK_SIZE+1);
  return strlen(buffer);
}

template <int P>
int pw(int a, int b) {
  ll ret = 1;
  while(b--) ret = ret * a % P;
  return ret;
}

template <int P, int Q>
bool verify(const int hlen, const int len, const pair<ll,ll>* hsh) {
  ll right = 0;
  ll left = 0;
  const ll mulblock = pw<P>(Q, BLOCK_SIZE);
  for(int i=0;i<hlen;++i) {
    left = left * mulblock;
    if(i+1 == hlen) right = right * pw<P>(Q, len);
    else right = right * mulblock;
    right = (right + hsh[i].second) % P;
    left = (left + hsh[hlen-1-i].first) % P;
  }
  return right == left;
}

bool solve() {
  int fst = read_buf();
  if(fst < BLOCK_SIZE) {
    for(int i=0;2*i<fst;++i)
      if(buffer[i] != buffer[fst-1-i]) return false;
    return true;
  }
  copy_n(buffer, fst, first_buf);
  int hlen = 0;
  hsh1[hlen] = ::hash<P1,Q1>(BLOCK_SIZE);
  hsh2[hlen++] = ::hash<P2,Q2>(BLOCK_SIZE);
  while(read_buf() == BLOCK_SIZE) {
    hsh1[hlen] = ::hash<P1,Q1>(BLOCK_SIZE);
    hsh2[hlen++] = ::hash<P2,Q2>(BLOCK_SIZE);
  }
  assert(hlen <= MAX_HSH);
  const int len = strlen(buffer);
  if(len == 0) {
    for(int i=0;i<hlen;++i) {
      if(hsh1[i].first != hsh1[hlen-1-i].second)
        return false;
      if(hsh2[i].first != hsh2[hlen-1-i].second)
        return false;
    }
    return true;
  }
  hsh1[hlen] = ::hash<P1,Q1>(len);
  hsh2[hlen++] = ::hash<P2,Q2>(len);

  return verify<P1,Q1>(hlen, len, hsh1) &&
         verify<P2,Q2>(hlen, len, hsh2);
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  string fst;
  getline(cin, fst);
  cout << (solve() ? "TAK\n" : "NIE\n" );
}