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
#include <bits/stdc++.h>

using namespace std;

vector <unsigned long long> mod = {4147090513LL, 4103161603LL, 799726727LL, 1936168183LL};
vector <unsigned long long> liczby = {9628443LL, 636319LL, 824602LL, 1688045LL, 9541486LL, 2889388LL, 3773778LL};
vector < pair <unsigned long long, unsigned long long> > pary;
vector < pair <unsigned long long, unsigned long long> > odwrotnosci;

vector <unsigned long long> wartosc_l;
vector <unsigned long long> wartosc_odwr;

unsigned long long pot(unsigned long long a, unsigned long long b, unsigned long long mod) {
	long long wynik = 1;	
	while (b > 0) {
		if (b % 2 == 1)
			wynik = (wynik * a) % mod;
		
		b /= 2;
		a = (a * a) % mod;
	}
	return wynik;
}

int main() {
	unsigned long long n, val1, val2;
	char litera;

	cin >> n;

	n = 0;
	for (int i = 0; i < mod.size(); i++)
		for (int j = 0; j < liczby.size(); j++)
			pary.push_back(make_pair(mod[i], liczby[j]));

	for (int i = 0; i < pary.size(); i++) {
		wartosc_l.push_back(0);
		wartosc_odwr.push_back(0);
		odwrotnosci.push_back(make_pair(pary[i].first, pot(pary[i].second, pary[i].first - 2, pary[i].first)));	
	}
	
	while (cin >> litera) {
		for (int i = 0; i < pary.size(); i++) {
			wartosc_l[i] = ((wartosc_l[i] * pary[i].second) % pary[i].first + (unsigned long long)litera) % pary[i].first;
		}			
		
		for (int i = 0; i < odwrotnosci.size(); i++) {
			wartosc_odwr[i] = ((wartosc_odwr[i] * odwrotnosci[i].second) % odwrotnosci[i].first + (unsigned long long)litera) % odwrotnosci[i].first;
		}
		n++;
	}
	
	for (int i = 0; i < pary.size(); i++) {
		val1 = wartosc_l[i];
		val2 = (wartosc_odwr[i] * pot(pary[i].second, n - 1, pary[i].first)) % pary[i].first;
		if (val1 != val2) {
			cout << "NIE\n";
			return 0;
		} 
	}
	cout << "TAK\n";
	return 0;
}