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
#include <tuple>
#include <vector>
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

using ll	= long long;
using ull	= unsigned long long;
using pii	= pair<int,int>;
using vi	= vector<int>;
using vb	= vector<bool>;
using vc	= vector<char>;
using vvi	= vector<vi>;
using vpii	= vector<pii>;
using vll	= vector<ll>;
using vull	= vector<ull>;

#define ever (;;)
#define f first
#define s second
#define pb emplace_back
#define sz size()
#define graph vector<vertex>
#define deg(X) G[X].e.size()
#define INF 1234567890
#define INFll 2000000000000000000
#define maxe(X, Y) if((Y) > (X)) (X) = (Y)
#define mine(X, Y) if((Y) < (X)) (X) = (Y)
#define rep(i, begin, end) for(__typeof(end) i = (begin); i < (end); ++i)
#define repr(i, begin, end) for(__typeof(end) i = (begin)-1; i >= (end); --i)
#define bend(X) X.begin(), X.end()

int n;

ll fastPow(ll x, ll p, ll mod) {
	if(p == 0)
		return 1;
	if(p&1)
		return (x*fastPow(x, p-1, mod))%mod;
	ll a = fastPow(x, p/2, mod);
	return (a*a)%mod;
}

struct Hash {
	Hash(ll p, ll m) : pw{p}, mod{m} {};
	const ll pw, mod;
	ll val = 0;
	void add(ll x) {
		val = (val*pw+x)%mod;
	}
};

struct TwoHash {
	TwoHash(ll p, ll m) : A{p, m}, B{fastPow(p, m-2, m), m}, mod{m}, pw{p} {};
	const ll pw, mod;
	Hash A, B;
	void add(ll x) {
		A.add(x);
		B.add(x);
	}
	bool get() {
		return A.val == ((B.val*fastPow(pw, n-1, mod))%mod);
	}
};

int main() {
	TwoHash H1{313ll, 1000000007ll};
	TwoHash H2{997ll, 1000000009ll};
	TwoHash H3{2137ll, 123597323ll};
	
	scanf("%d ", &n);
	n = 0;
	
	char c = getchar_unlocked();
	while(c >= 'a' && c <= 'z') {
		H1.add(c);
		H2.add(c);
		H3.add(c);
		c = getchar_unlocked();
		++n;
	}
	
	if(H1.get() && H2.get() && H3.get())
		printf("TAK\n");
	else
		printf("NIE\n");
	
	return 0;
}