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
#include <iostream>
#include <cctype>
#include <deque>
//#define cerr if(0)cout

using namespace std;

typedef long long ll;

const int duzo = 100000, mega = 20000007;
char *a;
int ile[26];
deque<char> deq;
const ll mod = 1234567891ll, pod = 599, podw = 861518161ll, pdd = 164060428ll;

ll p;
ll potega(ll w) {
  if(w == 1) return p;
  ll pom = potega(w / 2);
  pom *= pom;
  pom %= mod;
  if(w&1) {
    pom *= p;
    pom %= mod;
  }
  return pom;
}

inline ll pot(ll podst, ll w) {
  p = podst;
  return potega(w);
}

ll haprz, hatyl;

int main() {
  ios_base::sync_with_stdio(0);
  // cin.tie(0);
  int n;
  cin >> n;
  while(!isalpha(cin.peek())) cin.ignore();
  n = 0;
  char c;
  ll pprz = 1;
  ll ptyl = pdd;
  a = new char[duzo];
  while(!cin.eof()) {
    cin.get(c);
    if(isalpha(c)) {
      if(n < duzo) a[n] = c;
      ++n;
      if(n > duzo) deq.pop_front();
      deq.push_back(c);
      ++ile[c - 'a'];
      haprz += (ll)(c - 'a' + 1) * pprz;
      haprz %= mod;
      pprz *= pod;
      pprz %= mod;
      hatyl += (ll)(c - 'a' + 1) * ptyl;
      hatyl %= mod;
      ptyl *= podw;
      ptyl %= mod;
    }
    else {
      break;
    }
  }
  bool czypocz = true;
  for(int i = 0, s = min(duzo, n); i < s && czypocz; ++i) {
    c = deq.back();
    deq.pop_back();
    if(c != a[i]) czypocz = false;
  }
  if(!czypocz) {
    cout << "NIE";
    return 0;
  }
  delete[] a;
  ll dziel = pot(podw, mega - (n - 1));
  hatyl *= dziel;
  hatyl %= mod;
  if(haprz != hatyl) {
    cout << "NIE";
    return 0;
  }
  bool czyniep = false;
  for(int i = 'a'; i <= 'z'; ++i) {
    if((ile[i - 'a'])&1) {
      if(czyniep) {
        cout << "NIE";
        return 0;
      }
      else czyniep = true;
    }
  }
  cout << "TAK";
  return 0;
}