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
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bits/stdc++.h>


using namespace std;

#define int long long
int x1 = 353;
int x11 = 1;
int x2 = 577;
int x22 = 1;
int mod = 870078673ll; 
int h1 = 0, h2 = 0;
int h3 = 0, h4 = 0;


int32_t main()
{
  ios::sync_with_stdio(0);
  int n;
  cin >> n;

  int h1 = 0, h2 = 0;
  int h3 = 0, h4 = 0;

  char c;
  while(cin >> c)
  {
    h1 = (h1*x1 + c);//%mod2;
    h2 = (h2 + c*x11);//%mod2;

    h3 = (h3*x2 + c)%mod;
    h4 = (h4 + c*x22)%mod;

    x11 *= x1; // x11 %= mod2;
    x22 *= x2; x22 %= mod;
  }
  if(h1 == h2 && h3 == h4) cout << "TAK" << endl; else cout << "NIE" << endl;
}