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
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<iostream>
//#include<windows.h>
#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<map>
#include<iomanip>
#include<stack>
#include<queue>
#include<string>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<bitset>

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector< ii > vii;
typedef vector< pair < ii, int > > viii;
typedef vector< vector < ii > > vvii;
typedef pair < pair < int, int >, int >  iii;
typedef pair < pair < int, int >, pair < int, int > > iiii;
typedef unsigned long long ull;
typedef long long ll;
typedef unsigned long long ull;
typedef vector< ll > vll;
typedef long double ld;
typedef map < int, int > MAPA;

#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define st first
#define nd second
#define rep(i,n) for(int i=0; i<(n); ++i)
#define rall(c) (c).rbegin(), (c).rend()
#define FOR(i, a, b)    for (int (i)=(a); (i)<(b); (i)++)
#define FOR2(i, a, b)    for (int (i)=(a); (i)>=(b); (i)--)

template<typename T> inline void setmin(T &x, T y) { if (y < x) x = y; }
template<typename T> inline void setmax(T &x, T y) { if (y > x) x = y; }
template<typename T> inline T gcd(T a, T b) { while (b)swap(a %= b, b); return a; }

const int MAX = 2e6 + 7;
const int T = 1 << 20;
const int INF = 1e9 + 7;
const ll BIG_INF = 1e18 + 5;

ld e = 2.7182818284590452353602874713526624;
ld PI = acos(-1);
ld eps = 1e-19;

char znak;
ll n, m, k;

ll modulo[4] = { 1779459599, 1937421757 ,879699089 , 925978013 };
ll podstawa[4] = { 29 , 37 , 39 ,31}; 
ll odwrotnosci[4];
ll akt_hasz1[4] = {1 , 1 ,1 , 1};
ll akt_hasz2[4];
ll akt_suma1[4];
ll akt_suma2[4];

ll ust_dl = 20000007;

ll fast( ll a , ll x , ll p ){
	ll ret = 1;
	ll pom = a;

	while( x ){
		if( x & 1){
			ret = ( ret * pom ) % p;
		}
		pom = (pom * pom) % p;
		x >>= 1;
	}
	return ret;
}

int main() {
	boost;
	for( int i = 0 ; i < 2 ; i++ ){
		akt_hasz2[i] = fast( podstawa[i] , ust_dl , modulo[i] );
		odwrotnosci[i] = fast( podstawa[i] , modulo[i] - 2 , modulo[i] );
	}
	cin >> n;
	ll dl = 0;
	while( cin >> znak ){
		dl++;
		for( int i = 0 ; i < 2 ; i++ ){
			akt_suma2[i] = ( akt_suma2[i] + (int)( znak - 'a' ) * akt_hasz2[i])%modulo[i];
			akt_hasz2[i] = ( akt_hasz2[i] * odwrotnosci[i] ) % modulo[i];
			akt_suma1[i] = ( akt_suma1[i] + (int)( znak - 'a' ) * akt_hasz1[i])%modulo[i];
			akt_hasz1[i] = ( akt_hasz1[i] * podstawa[i] ) % modulo[i];
		}
	}

	bool good = 1;
	for( int i = 0 ; i < 2 ; i++ ){
		akt_suma1[i] = ( akt_suma1[i] * fast( podstawa[i] , ust_dl - dl + 1, modulo[i]) ) % modulo[i]; 
		//cout << akt_suma1[i] << ' ' << akt_suma2[i] << '\n';
		if( akt_suma1[i] != akt_suma2[i] ){
			good = 0;
		}
	}

	cout << ( good ? "TAK" : "NIE");

	
}