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
#include<cstdio>
#include<vector>
#include<algorithm>
#include<iostream>

using namespace std;

//std::ios::sync_with_stdio(false);

const long long P = 1000000007;
//const int ILE = 200007;

const long long ZIARNO = 64353;

//int hasze[ILE];

int power(long long a, int n, long long p)
{
  long long wyn = 1;
  long long tmp = a;
  for (int i = n; i > 0; i /= 2) {
    if (i % 2 == 1) {
      wyn = (wyn * tmp) % p;
    }
    tmp = (tmp*tmp) % p;
  }
  return wyn;
}

char nic[100];

int main() {
    
  int n;
  scanf("%i ", &n);
  //cin >> n;
  //cin.getline(nic, 100);
  n = 0;
  char c;
  //while (getchar() != 0x0A);
  //scanf("%c", &c);
  //cin >> c;
  //cin >> c;
  long long w = ZIARNO;
  long long v = power(w, P-2, P);
  long long lele = v;
  //printf("%i\n", (v*w) % P);
  int hszF = 0;
  int hszB = 0;
  while(  (c = getchar()) != EOF ) {
    //printf("wczytano %c\n", c);
    //scanf("%c",&c);
    if (c == 0x0A) break;
    //putchar(c);

    //hasz update
    hszF = (hszF + w * c) % P;
    hszB = (ZIARNO * hszB + c) % P;
    
    w = (w * ZIARNO) % P;
    v = (v * lele) % P;
    ++n;
  }
  //printf("\n%i\n", n);
  if ((lele * hszF)%P == hszB) {
    printf("TAK\n");
  }
  else {
    //printf("%lli %lli \n", (lele * hszF)%P, hszB);
    printf("NIE\n");
  }
  //printf("%i", '\n');
  
  
  return 0;
}