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
#include <cstdio>
const int P = 65697811, MOD = 1951323287;
int n;
char c;
unsigned long long hash[26], revhash[26], pow[26], sumpow[26];
int main() {
  scanf("%d\n", &n);
  n = 0;
  for (int i=0; i<26; i++) pow[i] = 1;
  while ((c = getchar()) >= 'a') {
    c -= 'a';
    hash[c] = (P * hash[c] + n) % MOD;
    revhash[c] = (revhash[c] + n * pow[c]) % MOD;
    sumpow[c] = (sumpow[c] + pow[c]) % MOD;
    pow[c] = (P * pow[c]) % MOD;
    n++;
  }
  bool ans = true;
  for (int i=0; i<26; i++) {
    unsigned long long x = ((n-1) * sumpow[i]) % MOD;
    x = (x + MOD - revhash[i]) % MOD;
    ans = (ans && x == hash[i]);
  }
  printf(ans ? "TAK\n" : "NIE\n");
  return 0;
}